0.1 Load necessary packages

computeFeatures: Compute object features


library(rvest) #webscraping package
library(jpeg) #convert scraped images to jpeg
library(xml2) #convert the xml from webpage into a list
library(dplyr)
library(EBImage) #image processing package. May require an R update 
#library(magick)
library(dendextend)
library(httr)
library(skimr)

library(cowplot)
library(ggdendro)
library(ggplot2)
library(ggimage) 


#library(pdftools) # Reads pdf names into text strings
library(tm) # Text cleaning for large corpa similar to tidytext it can help with cleaning and tokenizing
library(quanteda) # Text cleaning for large corpa similar to tidytext tokenizing
library(tidytext) # For analysis of text in a tidy manner including sentiment data
library(textstem) # For stemming and lemmatizing text
library(gutenbergr) # Project Gutenberg books
library(wordcloud) # For world cloud
# 
library(lsa) # For latent semantic analysis
library(stm) # For structural topic modeling
library(uwot) # For umap dimensionality reduction
library(text2vec) # For cosine similarity -
library(kernlab) # For kernel-based cannonical correlation analysis
library(rPref) # For pareto frontier\
library(DT) # For interactive data tables
library(textdata) # Database of lexicon and embeddings
# 
library(knitr)
library(ggrepel)
library(caret) # For predictive model fitting
library(tidyverse)
library(patchwork)
library(base)
# 
# set.seed(888)
# rm(list = ls()) 

0.2 Obtain high-level data of the chocolates (should only need to run once!)

When webscraping, there is a certain etiquette one should follow. If we send too many requests to a website at once, it can lead to the website banning us or putting us in “timeout” for requests. Therefore, it’s important in webscraping to be mindful of the number of requests you send. The first step I took was to gather the html data into a file, and then save the html file so we do not have to make additional requests at this step.

0.2.1 Scrape the data and save to html file

I have had a few instances where this caused by R to abort. Make sure you have enough RAM to read in the html file.


url = "https://gailambrosius.com/explore-flavors/learn-about-the-flavors"

get_object = GET(url)
cat(content(get_object, "text"), file="scrape.html") #save the url to an html file called scrape. 
Error in content(get_object, "text") : unused argument ("text")

rr simple = read_html(.html) info_links = as_list(html_nodes(simple, .popup)) #gets html info into parasable list

0.2.2 Build an initial dataframe of the chocolates

Figuring out how to parse through the html file was the most time consuming step. My strategy was to extract as much as I could from the main page, which included the names of the chocolates, link to the images, and links to the textual data. I started off extracting as many features as I could with the attribs list, so that I could see what data was available.


attribs = list("width", "height","src", ".class", "alt", "srcset", "sizes") #attributes that are available for the images that might be important

info.list = c(1:length(info_links)) #length of info_links information for referencing the right area
c.list = c() #get the list of chocolate names
src.list = c() #create a list of the image urls
descr.list= c() #create a list of the image descriptions

for(j in info.list){
    chocolate_img = info_links[j][[1]]$img #get url to the chocolate image
    chocolate_name = info_links[j][[1]]$div[[1]][1] #get the name of the chocolate
    descr_link = attr(info_links[j][[1]], "href") #get the link to the chocolate description 
  for(i in attribs){
    if (i == "src"){
      src.list = c(src.list,attr(chocolate_img, i) )
    }
  }
c.list =c(c.list, chocolate_name) #append chocolate names to a list 
descr.list = c(descr.list, descr_link) #apppend description urls to a list description list

}

df <- data.frame (  #create a dataframe of the chocolate names, images, and link to textual descriptions
                  name = c.list,
                  image_url = src.list,
                  d_list = descr.list
                  )


df[3,1] = "Cinnamon and Cayenne" #updated the name of Cinnamon and Cayenne because I found out later that because it was written as "Cinnamon/Cayenne", some functions were confused with the "/" symbol. 


df[11,1] = "Vanilla"

0.3 Clean and Prepare Text Descriptions of the Chocolates

0.3.1 Apply reader function to extract chocolate descriptions

I then created a function that is going to take the link of each chocolate and get the information. I used this function so that it could be applied to each column.

reader <- function(url) {
  
  simple= read_html(url) #changed this from "url"...see if this changes anything 

 x =  simple %>%
  html_nodes("p") %>%
  html_text()
 
 print(paste(x[1], x[2]), sep = " ")
  
}

I applied the reader function to the urls with textual data so I could systematically extract text. Ideally, you should only need to extract and run this function only once so that you are not scraping the webpage each time.


df$d_list <-as.character(df$d_list)
df["text"] = sapply(df$d_list, reader)
df$image_url <-as.character(df$image_url)

0.3.2 Tokenize and clean chocolate descriptions

In this step, I cleaned the textual data of the chocolate description using the methodology from Exercise 5.

## Clean data by "searches and replace" statements 
df$text = gsub('[0-9]+', '', df$text) # Removes words that include numbers
df$text = gsub('[.]+', '', df$text) # Removes words with periods
df$text = gsub('doi', '', df$text) # Removes non-word "doi"
df$text = gsub('fig', '', df$text) #
df$text = gsub('zij', '', df$text) 
df$text = gsub('nib', '', df$text) 
df$text = gsub("it's", '', df$text) 
df$text = gsub("It's", '', df$text) 
df$text = gsub("it", '', df$text) 
df$text = gsub("Tt", '', df$text) 
df$text = gsub("like", '', df$text)
df$text = gsub("just", '', df$text) 
df$text = gsub("madison", '', df$text)
df$text = gsub("Madison", '', df$text)
df$text = gsub("make", '', df$text)
df$text = gsub("kitchen", '', df$text)
## Tokenize based on word as token and remove punctuation and convert to lower case
text.df = df %>% 
    unnest_tokens(term, text, token = "words", 
                 to_lower = TRUE, 
                 strip_punct = TRUE) 
  
## Remove one-letter and two-letter words
  text.df = text.df %>% filter(str_length(term)>2)
  
## Remove very long words--spurious words created by pdf reader
  text.df = text.df %>% filter(str_length(term)<15)
  
## Remove stopwords
  text.df = text.df %>% 
    anti_join(get_stopwords(), by = c("term" = "word"))
  

#Stem and Lematize Wording

 text.df$term = stem_words(text.df$term) # Converts word to its stem, which might not be a word, such as "computational" >> "comput"
# Stem completion can convert back to a word based on the most frequent original form

text.df$term = lemmatize_words(text.df$term) # Similar to stemming, but returns a word and takes longer


## Plot number of words remaining after processing names
text.df %>% count(name) %>% 
ggplot(aes(n, reorder(name, -n))) +
  geom_col()+
  labs(x = "Total words for each chocolate type", y = " Chocolate Type")

NA
NA

The figure above shows the number of words remaining after cleaning and preprocessing of the textual data. Each chocolate seems to have a similar number of words remaining, so we are not too concerned with eliminating too many words from the data.

0.3.3 Weight term frequency, filter, and visualize terms using TFIDF

The more often a term occurs in a name the more indicative it is of the name’s content unless it term occurs frequently in most names. Term importance can be calculated as a combination of the local and global frequency using within-name term frequency (TF) and the inverse of its frequency across names (IDF). Reference: https://www.tidytextmining.com/tfidf.html

## Calculate term frequency and add tf_idf variables
tfidf.text.df = text.df %>% count(name, term) %>% 
  bind_tf_idf(term, name, n)


tfidf.text.df
NA

I created the plots from Exercise 5 to further understand the data. The chunk below is taking the dataframe we created above, and getting the top tf_idf for each of the chocolates, so we can determine the most defining words for the chocolate. Because there were not a lot of words and many disinctive words, I set n (the number of rows) in top_n to be 3.

## Plot most discriminating terms
top.df = tfidf.text.df %>% group_by(name) %>% top_n(3, tf_idf) %>% 
  ungroup() %>% 
  mutate(name = as.factor(name))

The first plot below provides insight into the most defining words of each chocolate. Multiple words appear for some chocolates because multiple words can appear with a similar frequency in each chocolate. The second plot investigates the tf vs. the idf in each chocolate. This is useful for understanding how often a word appears for a particular chocolate vs. how often it appears across all of the chocolates. For example, it makes sense that blueberry is very frequent for the blueberry chocoalte, and it also does not appear in the other chocolates.

ggplot(top.df, aes(reorder_within(term, tf_idf, within = name), tf_idf)) + ##increase the spacing between the words?
  geom_col() +
  coord_flip() +
  facet_wrap(.~name, scales = "free")+
  scale_x_reordered() 


# Scatterplot of term frequency and inverse name frequency for each name
ggplot(top.df, aes(idf, tf, size = tf_idf)) +
  geom_point(shape = 21, size = .75) +
  geom_text_repel(aes(label = term, size = tf_idf)) +
  facet_wrap(.~name) +
  theme_bw() +
  theme(legend.position = "none")


## A single plot of the top tf_idf terms across all names
ggplot(top.df, aes(idf, tf, size = tf_idf)) +
  geom_point(shape = 21, size = 1) +
  geom_text_repel(aes(label = term, size = tf_idf)) +
  theme_bw() +
  coord_trans(y="log") +
  theme(legend.position = "none")

0.3.4 LSA Space and Chocolate and Term Embeddings

# Convert from tidy format to termXChocolate matrix
tdm_weighted.tdmat = cast_tdm(tfidf.text.df, term, name, tf_idf)
tdm_count.tdmat = cast_tdm(tfidf.text.df, term, name, n)

lsa_model <- lsa(tdm_count.tdmat,  dims=dimcalc_share(share = .75)) 
# dimcalc_share retains that dimensions that retain the required share of the total variance

## Dimensions of the LSA space
# The singular value has a maximum dimensions of the number of chocolate
dim(lsa_model$tk) # Terms x LSA space
[1] 332  11
dim(lsa_model$dk) # Chococlate x LSA space
[1] 16 11
length(lsa_model$sk) # Singular values
[1] 11
## Shows expected value of word frequency for each chococolate
as.textmatrix(lsa_model)
$matrix
                 D1    D2    D3    D4    D5    D6    D7    D8    D9   D10   D11   D12
1. add         0.97  0.03  0.11 -0.13  0.13 -0.09  0.14  0.06  0.06  0.12 -0.10 -0.18
2. begin       1.00  0.09  0.72 -0.11 -0.08 -0.07  0.10 -0.29  0.07  0.00  0.07  0.21
3. berri       0.96 -0.06  0.11  0.03  0.00 -0.01 -0.03  0.10  0.11  0.00 -0.12  0.05
4. blueberri   3.81  0.05  0.18 -0.17 -0.07 -0.10  0.10  0.03  0.53  0.16 -0.51  0.17
5. bounti      0.95  0.01  0.05 -0.04 -0.02 -0.02  0.03  0.01  0.13  0.04 -0.13  0.04
6. box         1.09  1.01  0.92  0.13  1.08  0.04 -0.11 -0.11 -0.08  0.89  0.37  0.76
7. bright      0.93  0.20 -0.02 -0.02  0.64  0.20 -0.11 -0.02  0.06  0.07 -0.30  0.18
8. chocol      2.01  1.01  2.04  1.00  1.80  1.14  1.98  2.22  1.67  1.04  1.73  1.24
9. choic       1.00  1.01  1.01  0.98  1.07  0.96  1.02  0.96  1.08  1.02  1.06  0.88
10. coax       0.95  0.01  0.05 -0.04 -0.02 -0.02  0.03  0.01  0.13  0.04 -0.13  0.04
11. cream      1.96  1.26 -0.17  0.76  0.83  0.02  0.16  0.81  1.02  0.17 -0.17  0.06
12. danc       0.95  0.01  0.05 -0.04 -0.02 -0.02  0.03  0.01  0.13  0.04 -0.13  0.04
166. demand    0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
167. equal     0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
168. espresso  0.05 -0.05  0.15  0.50 -0.27  0.38  1.41  0.16  0.01 -0.27  0.17 -0.06
169. fair      0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
170. fulli     0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
171. hint     -0.10  0.06  0.27  0.09 -0.31  0.24  0.79  0.29  0.09  0.05  0.53  0.14
172. just      0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
173. lightli   0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
174. make      0.01 -0.21  0.20  0.27  0.05  0.06  0.76  0.21  0.06 -0.16  0.05  0.00
175. ride      0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
176. strong    0.05 -0.05  0.15  0.50 -0.27  0.38  1.41  0.16  0.01 -0.27  0.17 -0.06
177. trade     0.03 -0.03  0.08  0.25 -0.14  0.19  0.70  0.08  0.00 -0.14  0.09 -0.03
321. homemad  -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
322. ign      -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
323. kchen    -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
324. lifelong -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
325. lucil    -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
326. mom      -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
327. prefer   -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
328. pud      -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
329. spoon    -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
330. stovetop -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
331. tree     -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
332. winsom   -0.02 -0.19  0.13  0.02  0.18 -0.13  0.06  0.13  0.06 -0.02 -0.04  0.04
                D13   D14   D15   D16
1. add         0.02  0.87  0.01 -0.08
2. begin       0.04  0.08  0.07  0.11
3. berri      -0.06  0.02  0.97 -0.06
4. blueberri  -0.22  0.06  0.03 -0.08
5. bounti     -0.05  0.02  0.01 -0.02
6. box        -0.05  0.97 -0.01  0.06
7. bright     -0.11  0.17  0.03  0.16
8. chocol      1.19  2.06  2.97  3.02
9. choic       0.95  0.95  1.01  0.99
10. coax      -0.05  0.02  0.01 -0.02
11. cream      1.05  1.01  0.09  0.14
12. danc      -0.05  0.02  0.01 -0.02
166. demand   -0.18  0.12 -0.06  0.06
167. equal    -0.18  0.12 -0.06  0.06
168. espresso -0.35  0.24 -0.12  0.12
169. fair     -0.18  0.12 -0.06  0.06
170. fulli    -0.18  0.12 -0.06  0.06
171. hint     -0.17  0.14 -0.06  0.02
172. just     -0.18  0.12 -0.06  0.06
173. lightli  -0.18  0.12 -0.06  0.06
174. make     -0.14  0.06 -0.10  0.90
175. ride     -0.18  0.12 -0.06  0.06
176. strong   -0.35  0.24 -0.12  0.12
177. trade    -0.18  0.12 -0.06  0.06
321. homemad   0.03 -0.06 -0.04  0.84
322. ign       0.03 -0.06 -0.04  0.84
323. kchen     0.03 -0.06 -0.04  0.84
324. lifelong  0.03 -0.06 -0.04  0.84
325. lucil     0.03 -0.06 -0.04  0.84
326. mom       0.03 -0.06 -0.04  0.84
327. prefer    0.03 -0.06 -0.04  0.84
328. pud       0.03 -0.06 -0.04  0.84
329. spoon     0.03 -0.06 -0.04  0.84
330. stovetop  0.03 -0.06 -0.04  0.84
331. tree      0.03 -0.06 -0.04  0.84
332. winsom    0.03 -0.06 -0.04  0.84

$legend
 [1] "D1 = Blueberry"                        "D2 = Caramel Sprinkled With Grey Salt"
 [3] "D3 = Cinnamon and Cayenne"             "D4 = Cognac"                          
 [5] "D5 = Cointreau"                        "D6 = Earl Grey"                       
 [7] "D7 = Espresso"                         "D8 = Featured Single Origin"          
 [9] "D9 = Jasmine"                          "D10 = Lemongrass with Ginger"         
[11] "D11 = Machu Picchu"                    "D12 = Raspberry"                      
[13] "D13 = Rose"                            "D14 = Shiitake Mushroom"              
[15] "D15 = Sweet Curry With Saffron"        "D16 = Vanilla"                        
## Calculates LSA on tf_idf weighted terms
lsa_model = lsa(tdm_weighted.tdmat,  dims=dimcalc_share(share = .75))

rm(tdm_count.tdmat)

0.4 Cluster chocolates by terms-AGNES using the LSA Embeddings

Once I had the textual data of chococlates from the LSA embeddings, I conducted AGNES hierarchical clustering using the embeddings.


## Cosine similarity is equal to 1 for identical documents
doc.similiarity.mat = cosine(t(lsa_model$dk)) # The d component describes the documents 

## Calculates the mean tf_idf of each term and selects top 70 
temp = tfidf.text.df %>% 
  group_by(term) %>% 
  summarise(m.tf_idf = mean(tf_idf)) %>% 
  cbind(lsa_model$tk) %>% top_n(70, m.tf_idf) 

# Cosine similarity of terms
row.names(temp)= temp$term
term.similiarity.mat = cosine(t(temp %>% select(-term, -m.tf_idf))) 

doc.dissimilarity.dist = as.dist(1-doc.similiarity.mat)
term.dissimilarity.dist = as.dist(1-term.similiarity.mat)

## Hierarchical clustering
# Setting method = ward.d2 corresponds to agnes clustering
doc.cluster = hclust(doc.dissimilarity.dist, method = "ward.D2", members = NULL)
dend_lsa <- as.dendrogram (doc.cluster)
## Build the dendrogram with the images of the chocolates for the LSA embeddings 

image_lsa.df <- data.frame(y = seq(1,32, by = 2),
                x = c(.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1, -.1),
                image = c("Sweet Curry With Saffron.jpeg",
                                 "Cognac.jpeg",  "Lemongrass with Ginger.jpeg","Jasmine.jpeg", "Rose.jpeg", "Vanilla.jpeg", "Cinnamon and Cayenne.jpeg", "Machu Picchu.jpeg", "Blueberry.jpeg", "Raspberry.jpeg", "Caramel Sprinkled With Grey Salt.jpeg", "Shiitake Mushroom.jpeg", "Espresso.jpeg", "Featured Single Origin.jpeg", "Cointreau.jpeg", "Earl Grey.jpeg"))

choc_dend = ggdendrogram(dend_lsa, rotate = TRUE, theme_dendro = TRUE, cex = 100) #+ theme(axis.text.x = element_text(size=14))


#ggdendrogram(dend1, rotate = TRUE, theme_dendro = TRUE)
labels = ggplot(image_lsa.df, aes(x, y)) + geom_image(aes(image=image), size=.125) +  theme_bw() + theme(panel.border = element_blank(), panel.grid.major = element_blank(),
panel.grid.minor = element_blank(), axis.line = element_line(colour = "white"), axis.ticks.x = element_blank(),
        axis.text.y = element_blank(),
        axis.ticks.y = element_blank(), axis.text.x = element_blank(),axis.title.x = element_text(color = "white"),
axis.title.y = element_blank())  + xlim(-.25, .25) 

layout <- c(
  area(t = 1, l = 1, b = 1, r = 2),
  area(t = 1, l = 3, b = 1, r = 4)
)



labels+ choc_dend +plot_layout(design = layout)

0.5 Cluster chocolates by terms-AGNES using the GLOVE Embeddings

I wanted to see how the embeddings used changes the outcome of the dendrogram, so I created the same dendrogram using the GLOVE embeddings. You should only need to read in the GLOVE Embeddings once as well.

Import the glove embeddings (should only need to do this once!)

## Similar to sentiment lexicon, word embeddings can be added to describe the terms in documents

glove = read_delim(file = "glove.6B/glove.6B.300d.txt", 
                   progress =FALSE,
                    col_names = FALSE, delim = " ", quote = "")
 names(glove)[1] = "token"
glovec.text.df = text.df %>% 
  inner_join(glove, by=c("term" = "token"))

rr ## Document embeddings can be created by averaging the term embedding s.glovec.text.df = glovec.text.df %>% gather(key = glovec_id, value = glovalue, contains()) %>% group_by(name, glovec_id) %>% summarise(m.glovalue = mean(glovalue)) %>% spread(key = glovec_id, value = m.glovalue) %>% ungroup()

`summarise()` has grouped output by 'name'. You can override using the `.groups` argument.

rr ## Calculate document distance based on cosine similarity of generic embedding

doc.similiarity.mat = cosine(t(s.glovec.text.df %>% select(contains()) %>% as.matrix()))
row.names(doc.similiarity.mat) = as.vector(s.glovec.text.df$name)

doc.dissimilarity.dist = as.dist(1-doc.similiarity.mat)

doc.cluster = hclust(doc.dissimilarity.dist, method = .D2, members = NULL) doc.cluster


Call:
hclust(d = doc.dissimilarity.dist, method = \ward.D2\, members = NULL)

Cluster method   : ward.D2 
Number of objects: 16 

rr dend_glove <- as.dendrogram (doc.cluster)

#ggdendrogram(dend_glove, rotate = TRUE, theme_dendro = TRUE)

rr ## Build the dendrogram with the images of the chocolates for the GLOVE embeddings image_glove.df <- data.frame(y = seq(1,32, by = 2), x = c(.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1, -.1), image = c(with Ginger.jpeg, Mushroom.jpeg, .jpeg, Curry With Saffron.jpeg, .jpeg, .jpeg, Sprinkled With Grey Salt.jpeg, and Cayenne.jpeg, Picchu.jpeg, .jpeg, .jpeg, Single Origin.jpeg, Grey.jpeg, .jpeg, .jpeg, .jpeg))

choc_dend = ggdendrogram(dend_glove, rotate = TRUE, theme_dendro = TRUE, cex = 100)

labels = ggplot(image_glove.df, aes(x, y)) + geom_image(aes(image=image), size=.125) + theme_bw() + theme(panel.border = element_blank(), panel.grid.major = element_blank(), panel.grid.minor = element_blank(), axis.line = element_line(colour = ), axis.ticks.x = element_blank(), axis.text.y = element_blank(), axis.ticks.y = element_blank(), axis.text.x = element_blank(),axis.title.x = element_text(color = ), axis.title.y = element_blank()) + xlim(-.25, .25)

layout <- c( area(t = 1, l = 1, b = 1, r = 2), area(t = 1, l = 3, b = 1, r = 4) )

labels+ choc_dend +plot_layout(design = layout)

0.6 Clean and Prepare Morphological and Textural Features of Images

My strategy for getting data on the images was to take the df we had built for the text-analysis and use the URLs to extract images from the website and then extract the image data. In this step, I am extracting the morphological features and textural features of images. The morphological feautres relate to physical structure of different regions of an image. The textural features investigate the spatial arrangements and and color intensities of an image. It relates to the patterns in the pixels themselves. Description of the haralick features: asm - angular second moment –> measure of uniformity. Reaches it’s highest point when grey level distribution has constant or periodic form con - contrast –> measure of local variations in an image cor - correlation –> measure of image linearity (high correlation means very linear image) var - variance – > variance in the textural idm - inverse difference moment –> measure image homogeneity sav- sum average sva - sum variance sen - sum entropy ent - entropy –> randomness in the intensity distribution dva - difference variance den - difference entropy f12 - measure of correlation –> information measures of correlation f13- measuer of correlation –> information measures of correlation

Download jpegs of chocolates (should only need to do this once)

for (i in 1:nrow(df)) #using the previously constructed data frame, we can use the URLs to get the images and find the image features
{
  choc_name = df["name"][i,] #get the name of the chocolate
  url = df["image_url"][i,] #get the url for the image of the chocolate 
  download.file(url, paste(choc_name,".jpeg", sep=""), mode = "wb") #download the jpeg file
  file_name = paste(choc_name,".jpeg", sep="") #save the jpeg file to the directory for easy access
}
trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-blueberry.jpg'
Content type 'image/jpeg' length 7068 bytes
==================================================
downloaded 7068 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-caramel.jpg'
Content type 'image/jpeg' length 6338 bytes
==================================================
downloaded 6338 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-cinnamon.jpg'
Content type 'image/jpeg' length 5636 bytes
==================================================
downloaded 5636 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-cognac.jpg'
Content type 'image/jpeg' length 6973 bytes
==================================================
downloaded 6973 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-cointreau.jpg'
Content type 'image/jpeg' length 7334 bytes
==================================================
downloaded 7334 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-earlgrey.jpg'
Content type 'image/jpeg' length 6911 bytes
==================================================
downloaded 6911 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-espresso.jpg'
Content type 'image/jpeg' length 6998 bytes
==================================================
downloaded 6998 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-rica.jpg'
Content type 'image/jpeg' length 7382 bytes
==================================================
downloaded 7382 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-jasmine.jpg'
Content type 'image/jpeg' length 6903 bytes
==================================================
downloaded 6903 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-lemongrass.jpg'
Content type 'image/jpeg' length 7261 bytes
==================================================
downloaded 7261 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/lucillesvanilla.jpg'
Content type 'image/jpeg' length 5973 bytes
==================================================
downloaded 5973 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-maccupiccu.jpg'
Content type 'image/jpeg' length 7442 bytes
==================================================
downloaded 7442 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-raspberry.jpg'
Content type 'image/jpeg' length 7868 bytes
==================================================
downloaded 7868 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-rose.jpg'
Content type 'image/jpeg' length 6908 bytes
==================================================
downloaded 6908 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-shiitake.jpg'
Content type 'image/jpeg' length 7550 bytes
==================================================
downloaded 7550 bytes

trying URL 'https://gailambrosius.com/wp-content/uploads/2013/08/flavor-curry.jpg'
Content type 'image/jpeg' length 8133 bytes
==================================================
downloaded 8133 bytes
#this gets all of the necessary jpegs
#for (i in 1:nrow(df))
df_test = data.frame()

# for (i in 1:nrow(df)) #using the previously constructed data frame, we can use the URLs to get the images and find the image features
# {
  choc_name = df["name"][1,] #get the name of the chocolate
  
  file_name = paste(choc_name,".jpeg", sep="")
  Image = readImage(file_name) #this is where I had the issue with Cinnamon and Cayenne  
  
  Image3<-getFrame(Image,2) #I had an issue with the images being read in by R as a vpVideo, so I had t to grab a frame of the video for the proceeding functions to work. I noticed that the selected frame did not matter. So, in this instance we are picking frame 2. 
  x = thresh(Image3, w=45, h=45, offset=0.05) #This creates the "window" of the image. This is important because all of the images need to be the same size in the proceeding steps. I figured out whcih dimensions worked from trial and error. 
  
  x = opening(x, makeBrush(3, shape='diamond')) #opening function removes morphological noise from images and removes small objects from the background. I adjusted the size and shape to read in the image as accuratley as possible
  x = bwlabel(x) #Image must be 2D to be compute the morphological and textur features 
  #display(x)  #this will show you what the image so you can see how R reads the image
  fts = computeFeatures.shape(x) #computing morphological (shape) features of the image 

#display(x)
  
#begin building the morphological features
morph = fts %>%
  as_tibble() %>%
  mutate(across(.cols = everything(), list(mean = mean, sd = sd))) %>% #extract the mean and standard o deviation of each of the morphological features because they return multiple rows 
  mutate(count = n()) %>% #get the count of the number of "clusters" identified in the images
  select(s.area_mean:s.radius.max_mean) #extract only the mean and standard deviatinos of features

morph = head(morph, 1) #keep only the first row 
morph[is.na(morph)] = 0

morph$name = choc_name #so that I can join with haralick features later

text_feat <- computeFeatures.haralick(x, Image3)# get textural features of the images

text_feat.df = as.data.frame(text_feat) #convert to df to simplify manipulation 

haralickFeatures = text_feat.df %>% 
  as_tibble() %>%
  mutate(across(.cols = everything(), list(mean = mean, sd = sd))) %>%
  select(h.asm.s1_mean:h.f13.s2_sd) #remove columns taht are not a mean or sd value
haralickFeatures  = head(haralickFeatures, 1) #remove the first row since it duplicates

haralickFeatures$name = choc_name #assign chocolate name so that it can merge with morph features later

haralickFeatures[is.na(haralickFeatures)] = 0 #turn any NAs to 0
#print(haralickFeatures)

final = merge(haralickFeatures, morph) #merge the morphological and haralick features for the chocolate

df_test = rbind(df_test, final) #Merge with other rows

# }

I investigated the columns to see what information might be worth keeping in. Based on what I knew about the data, I knew that the most obvious difference in chocolates was with the cinnamon/cayenne and the other flavors. So, I was sure to keep columns that signified this difference. I dropped columns that had a very large scale that might heavily skew the distances in the data, such as the sum of the averages and the sum of the variances.

drop.df = df_test %>%  #drop columns that were not relevant and increased dendrogram scale considerably
  select(-h.sva.s1_mean, -h.sva.s1_sd, -h.sav.s1_mean, -h.sav.s1_sd, -h.sva.s2_mean, -h.sva.s2_sd, -h.sav.s2_mean, -h.sav.s2_sd, -s.area_mean, -s.area_sd, -s.perimeter_mean, -s.perimeter_sd, -s.area_mean, -s.area_sd)

#I kept all of the textural features


drop.df

drop.df[2,1] = "Caramel with Salt"
drop.df[8,1] = "Single Origin"
drop.df[10,1] = "Lemon and Ginger"

Prepare data with removing NA and scaling.


scaled.df = drop.df %>% 
  drop_na() %>%  # Removes rows with missing data 
  select(-name) %>%
  scale() %>% as.data.frame()

scaled.df
NA

0.7 Cluster chocolates and images-AGNES using the Textural and Morphological Features



row.names(scaled.df) = as.vector(drop.df$name)


res.dist = dist(scaled.df, method = "euclidean")
hc2 <- hclust(res.dist, method = "ward.D2") #uses agnes method

 dend_im <- as.dendrogram (hc2)

#ggdendrogram(dend_im, rotate = TRUE, theme_dendro = TRUE)

The results of the images are somewhat as expected! We can see that cinnamon/cayenne is in its own grouping, which makes sense because it is powdered and has no luster in the image. Interestingly enough, something I noticed was how Espresso is not with Cointreau, Cognac and Vanilla. This reveals some noise in the data because Espresso has quite a bit of shine on the top which make the algorithm think the Espresso has a lot of parts on it in the middle similar to the Blueberry and Earl Grey.


 image_mt.df <- data.frame(y = seq(1,32, by = 2),
                x = c(.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1,-.1,.1, -.1),
                image = c("Cinnamon and Cayenne.jpeg",
                                 "Shiitake Mushroom.jpeg", "Sweet Curry With Saffron.jpeg", "Cointreau.jpeg", "Cognac.jpeg", "Vanilla.jpeg", "Featured Single Origin.jpeg", "Caramel Sprinkled With Grey Salt.jpeg", "Raspberry.jpeg", "Machu Picchu.jpeg", "Jasmine.jpeg", "Lemongrass with Ginger.jpeg", "Blueberry.jpeg", "Espresso.jpeg", "Earl Grey.jpeg", "Rose.jpeg"))

choc_dend = ggdendrogram(dend_im, rotate = TRUE, theme_dendro = TRUE, cex = 100) 


#ggdendrogram(dend1, rotate = TRUE, theme_dendro = TRUE)
labels = ggplot(image_mt.df , aes(x, y)) + geom_image(aes(image=image), size=.125) +  theme_bw() + theme(panel.border = element_blank(), panel.grid.major = element_blank(),
panel.grid.minor = element_blank(), axis.line = element_line(colour = "white"), axis.ticks.x = element_blank(),
        axis.text.y = element_blank(),
        axis.ticks.y = element_blank(), axis.text.x = element_blank(),axis.title.x = element_text(color = "white"),
axis.title.y = element_blank())  + xlim(-.25, .25) 

layout <- c(
  area(t = 1, l = 1, b = 1, r = 2),
  area(t = 1, l = 3, b = 1, r = 4)
)



labels+ choc_dend +plot_layout(design = layout)

Now that all of the dendrograms are made, I wanted to ensure that they have all the same labels just in case!

sort(labels(dend1)) == sort(labels(dend2)) #verify all the labels are the same
 [1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE

0.8 Tanglegrams

0.8.1 Tanglegram of GLOVE word embeddings and Images

The engtanglement measures the quality of the alignment between the two trees. The lower the entanglement is, the better (1 =full entanglement, 0 = no entanglement)


dend = dendlist(dend1, dend2) %>% #left hand side is the textual data, and the right hand side are the images 
  untangle(method = "step1side") %>% # Find the best alignment layout
  tanglegram(lab.cex = .9, margin_inner = 9, common_subtrees_color_branches = TRUE) # Color common branches)                       # Draw the two dendrograms

dend %>% plot(main = paste("entanglement =", round(entanglement(dend), 2))) #the engtanglement measures the quality of the alignment between the two trees. The lower the entanglement is, the better  (1 =full entanglement, 0 = no entanglement)

NA
NA

My conclusion for this tanglegram is that it is “better than nothing”.

0.8.2 Tanglegram of Images and LSA embeddings

dend = dendlist(dend2, dend3) %>% #left hand side is the textual data, and the right hand side are the images 
  untangle(method = "step1side") %>% # Find the best alignment layout
  tanglegram(lab.cex = .9, margin_inner = 9, common_subtrees_color_branches = TRUE) # Color common branches)                       # Draw the two dendrograms
Error in match_order_by_labels(dend2, dend1) : 
  labels do not match in both trees.  Please make sure to fix the labels names!
(make sure also that the labels of BOTH trees are 'character')

Tanglegram for the LSA and images reveal a relatively high entanglement. Not much commonality in the clustering results.

0.8.3 Tanglegram of LSA embeddings and GLOVE embeddings

rr dend = dendlist(dend1, dend3) %>% #left hand side is the textual data, and the right hand side are the images untangle(method = 1side) %>% # Find the best alignment layout tanglegram(lab.cex = .9, margin_inner = 9, common_subtrees_color_branches = TRUE) # Color common branches) # Draw the two dendrograms

rr dend %>% plot(main = paste(=, round(entanglement(dend), 2))) #the engtanglement measures the quality of the alignment between the two trees. The lower the entanglement is, the better (1 =full entanglement, 0 = no entanglement)

rr NA NA

Tanglegram for the LSA and word embeddings reveal a relatively high entanglement. Not much commonality in the clustering results. An important takeaway is that the approach taken with text-analysis can highly vary the constructed dendrogram.

LS0tCnRpdGxlOiAiQ2x1c3RlcmluZyBHYWlsIEFtYnJvc2l1cyBDaG9jb2xhdGUncyBCeSBJbWFnZXMgYW5kIFRleHR1YWwgRGVzY3JpcHRpb24gIgphdXRob3I6ICJTb2ZpYSBJc2FiZWwgTm9lam92aWNoLCBKb2huIExlZSIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKLS0tCgojIyBMb2FkIG5lY2Vzc2FyeSBwYWNrYWdlcyAKY29tcHV0ZUZlYXR1cmVzOiBDb21wdXRlIG9iamVjdCBmZWF0dXJlcwoKCmBgYHtyIGxvYWRfcGFja2FnZXMsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CgpsaWJyYXJ5KHJ2ZXN0KSAjd2Vic2NyYXBpbmcgcGFja2FnZQpsaWJyYXJ5KGpwZWcpICNjb252ZXJ0IHNjcmFwZWQgaW1hZ2VzIHRvIGpwZWcKbGlicmFyeSh4bWwyKSAjY29udmVydCB0aGUgeG1sIGZyb20gd2VicGFnZSBpbnRvIGEgbGlzdApsaWJyYXJ5KGRwbHlyKQpsaWJyYXJ5KEVCSW1hZ2UpICNpbWFnZSBwcm9jZXNzaW5nIHBhY2thZ2UuIE1heSByZXF1aXJlIGFuIFIgdXBkYXRlIAojbGlicmFyeShtYWdpY2spCmxpYnJhcnkoZGVuZGV4dGVuZCkKbGlicmFyeShodHRyKQpsaWJyYXJ5KHNraW1yKQoKbGlicmFyeShjb3dwbG90KQpsaWJyYXJ5KGdnZGVuZHJvKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoZ2dpbWFnZSkgCgoKI2xpYnJhcnkocGRmdG9vbHMpICMgUmVhZHMgcGRmIG5hbWVzIGludG8gdGV4dCBzdHJpbmdzCmxpYnJhcnkodG0pICMgVGV4dCBjbGVhbmluZyBmb3IgbGFyZ2UgY29ycGEgc2ltaWxhciB0byB0aWR5dGV4dCBpdCBjYW4gaGVscCB3aXRoIGNsZWFuaW5nIGFuZCB0b2tlbml6aW5nCmxpYnJhcnkocXVhbnRlZGEpICMgVGV4dCBjbGVhbmluZyBmb3IgbGFyZ2UgY29ycGEgc2ltaWxhciB0byB0aWR5dGV4dCB0b2tlbml6aW5nCmxpYnJhcnkodGlkeXRleHQpICMgRm9yIGFuYWx5c2lzIG9mIHRleHQgaW4gYSB0aWR5IG1hbm5lciBpbmNsdWRpbmcgc2VudGltZW50IGRhdGEKbGlicmFyeSh0ZXh0c3RlbSkgIyBGb3Igc3RlbW1pbmcgYW5kIGxlbW1hdGl6aW5nIHRleHQKbGlicmFyeShndXRlbmJlcmdyKSAjIFByb2plY3QgR3V0ZW5iZXJnIGJvb2tzCmxpYnJhcnkod29yZGNsb3VkKSAjIEZvciB3b3JsZCBjbG91ZAojIApsaWJyYXJ5KGxzYSkgIyBGb3IgbGF0ZW50IHNlbWFudGljIGFuYWx5c2lzCmxpYnJhcnkoc3RtKSAjIEZvciBzdHJ1Y3R1cmFsIHRvcGljIG1vZGVsaW5nCmxpYnJhcnkodXdvdCkgIyBGb3IgdW1hcCBkaW1lbnNpb25hbGl0eSByZWR1Y3Rpb24KbGlicmFyeSh0ZXh0MnZlYykgIyBGb3IgY29zaW5lIHNpbWlsYXJpdHkgLQpsaWJyYXJ5KGtlcm5sYWIpICMgRm9yIGtlcm5lbC1iYXNlZCBjYW5ub25pY2FsIGNvcnJlbGF0aW9uIGFuYWx5c2lzCmxpYnJhcnkoclByZWYpICMgRm9yIHBhcmV0byBmcm9udGllclwKbGlicmFyeShEVCkgIyBGb3IgaW50ZXJhY3RpdmUgZGF0YSB0YWJsZXMKbGlicmFyeSh0ZXh0ZGF0YSkgIyBEYXRhYmFzZSBvZiBsZXhpY29uIGFuZCBlbWJlZGRpbmdzCiMgCmxpYnJhcnkoa25pdHIpCmxpYnJhcnkoZ2dyZXBlbCkKbGlicmFyeShjYXJldCkgIyBGb3IgcHJlZGljdGl2ZSBtb2RlbCBmaXR0aW5nCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShiYXNlKQojIAojIHNldC5zZWVkKDg4OCkKIyBybShsaXN0ID0gbHMoKSkgCmBgYAogCiMjIE9idGFpbiBoaWdoLWxldmVsIGRhdGEgb2YgdGhlIGNob2NvbGF0ZXMgKHNob3VsZCBvbmx5IG5lZWQgdG8gcnVuIG9uY2UhKQpXaGVuIHdlYnNjcmFwaW5nLCB0aGVyZSBpcyBhIGNlcnRhaW4gZXRpcXVldHRlIG9uZSBzaG91bGQgZm9sbG93LiBJZiB3ZSBzZW5kIHRvbyBtYW55IHJlcXVlc3RzIHRvIGEgd2Vic2l0ZSBhdCBvbmNlLCBpdCBjYW4gbGVhZCB0byB0aGUgd2Vic2l0ZSBiYW5uaW5nIHVzIG9yIHB1dHRpbmcgdXMgaW4gInRpbWVvdXQiIGZvciByZXF1ZXN0cy4gVGhlcmVmb3JlLCBpdCdzIGltcG9ydGFudCBpbiB3ZWJzY3JhcGluZyB0byBiZSBtaW5kZnVsIG9mIHRoZSBudW1iZXIgb2YgcmVxdWVzdHMgeW91IHNlbmQuIFRoZSBmaXJzdCBzdGVwIEkgdG9vayB3YXMgdG8gZ2F0aGVyIHRoZSBodG1sIGRhdGEgaW50byBhIGZpbGUsIGFuZCB0aGVuIHNhdmUgdGhlIGh0bWwgZmlsZSBzbyB3ZSBkbyBub3QgaGF2ZSB0byBtYWtlIGFkZGl0aW9uYWwgcmVxdWVzdHMgYXQgdGhpcyBzdGVwLiAKCiMjIyBTY3JhcGUgdGhlIGRhdGEgYW5kIHNhdmUgdG8gaHRtbCBmaWxlIApJIGhhdmUgaGFkIGEgZmV3IGluc3RhbmNlcyB3aGVyZSB0aGlzIGNhdXNlZCBieSBSIHRvIGFib3J0LiBNYWtlIHN1cmUgeW91IGhhdmUgZW5vdWdoIFJBTSB0byByZWFkIGluIHRoZSBodG1sIGZpbGUuCgpgYGB7ciBHZXQgaW5mbyBmcm9tIHdlYnNpdGV9Cgp1cmwgPSAiaHR0cHM6Ly9nYWlsYW1icm9zaXVzLmNvbS9leHBsb3JlLWZsYXZvcnMvbGVhcm4tYWJvdXQtdGhlLWZsYXZvcnMiCgpnZXRfb2JqZWN0ID0gR0VUKHVybCkKY2F0KGNvbnRlbnQoZ2V0X29iamVjdCwgInRleHQiKSwgZmlsZT0ic2NyYXBlLmh0bWwiKSAjc2F2ZSB0aGUgdXJsIHRvIGFuIGh0bWwgZmlsZSBjYWxsZWQgc2NyYXBlLiAKYGBgCgpgYGB7cn0Kc2ltcGxlID0gcmVhZF9odG1sKCJzY3JhcGUuaHRtbCIpCmluZm9fbGlua3MgPSBhc19saXN0KGh0bWxfbm9kZXMoc2ltcGxlLCAiLnBvcHVwIikpICNnZXRzIGh0bWwgaW5mbyBpbnRvIHBhcmFzYWJsZSBsaXN0IAoKYGBgCgojIyMgQnVpbGQgYW4gaW5pdGlhbCBkYXRhZnJhbWUgb2YgdGhlIGNob2NvbGF0ZXMKRmlndXJpbmcgb3V0IGhvdyB0byBwYXJzZSB0aHJvdWdoIHRoZSBodG1sIGZpbGUgd2FzIHRoZSBtb3N0IHRpbWUgY29uc3VtaW5nIHN0ZXAuIE15IHN0cmF0ZWd5IHdhcyB0byBleHRyYWN0IGFzIG11Y2ggYXMgSSBjb3VsZCBmcm9tIHRoZSBtYWluIHBhZ2UsIHdoaWNoIGluY2x1ZGVkIHRoZSBuYW1lcyBvZiB0aGUgY2hvY29sYXRlcywgbGluayB0byB0aGUgaW1hZ2VzLCBhbmQgbGlua3MgdG8gdGhlIHRleHR1YWwgZGF0YS4gSSBzdGFydGVkIG9mZiBleHRyYWN0aW5nIGFzIG1hbnkgZmVhdHVyZXMgYXMgSSBjb3VsZCB3aXRoIHRoZSBhdHRyaWJzIGxpc3QsIHNvIHRoYXQgSSBjb3VsZCBzZWUgd2hhdCBkYXRhIHdhcyBhdmFpbGFibGUuCgpgYGB7cn0KCmF0dHJpYnMgPSBsaXN0KCJ3aWR0aCIsICJoZWlnaHQiLCJzcmMiLCAiLmNsYXNzIiwgImFsdCIsICJzcmNzZXQiLCAic2l6ZXMiKSAjYXR0cmlidXRlcyB0aGF0IGFyZSBhdmFpbGFibGUgZm9yIHRoZSBpbWFnZXMgdGhhdCBtaWdodCBiZSBpbXBvcnRhbnQKCmluZm8ubGlzdCA9IGMoMTpsZW5ndGgoaW5mb19saW5rcykpICNsZW5ndGggb2YgaW5mb19saW5rcyBpbmZvcm1hdGlvbiBmb3IgcmVmZXJlbmNpbmcgdGhlIHJpZ2h0IGFyZWEKYy5saXN0ID0gYygpICNnZXQgdGhlIGxpc3Qgb2YgY2hvY29sYXRlIG5hbWVzCnNyYy5saXN0ID0gYygpICNjcmVhdGUgYSBsaXN0IG9mIHRoZSBpbWFnZSB1cmxzCmRlc2NyLmxpc3Q9IGMoKSAjY3JlYXRlIGEgbGlzdCBvZiB0aGUgaW1hZ2UgZGVzY3JpcHRpb25zCgpmb3IoaiBpbiBpbmZvLmxpc3QpewogICAgY2hvY29sYXRlX2ltZyA9IGluZm9fbGlua3Nbal1bWzFdXSRpbWcgI2dldCB1cmwgdG8gdGhlIGNob2NvbGF0ZSBpbWFnZQogICAgY2hvY29sYXRlX25hbWUgPSBpbmZvX2xpbmtzW2pdW1sxXV0kZGl2W1sxXV1bMV0gI2dldCB0aGUgbmFtZSBvZiB0aGUgY2hvY29sYXRlCiAgICBkZXNjcl9saW5rID0gYXR0cihpbmZvX2xpbmtzW2pdW1sxXV0sICJocmVmIikgI2dldCB0aGUgbGluayB0byB0aGUgY2hvY29sYXRlIGRlc2NyaXB0aW9uIAogIGZvcihpIGluIGF0dHJpYnMpewogICAgaWYgKGkgPT0gInNyYyIpewogICAgICBzcmMubGlzdCA9IGMoc3JjLmxpc3QsYXR0cihjaG9jb2xhdGVfaW1nLCBpKSApCiAgICB9CiAgfQpjLmxpc3QgPWMoYy5saXN0LCBjaG9jb2xhdGVfbmFtZSkgI2FwcGVuZCBjaG9jb2xhdGUgbmFtZXMgdG8gYSBsaXN0IApkZXNjci5saXN0ID0gYyhkZXNjci5saXN0LCBkZXNjcl9saW5rKSAjYXBwcGVuZCBkZXNjcmlwdGlvbiB1cmxzIHRvIGEgbGlzdCBkZXNjcmlwdGlvbiBsaXN0Cgp9CgpkZiA8LSBkYXRhLmZyYW1lICggICNjcmVhdGUgYSBkYXRhZnJhbWUgb2YgdGhlIGNob2NvbGF0ZSBuYW1lcywgaW1hZ2VzLCBhbmQgbGluayB0byB0ZXh0dWFsIGRlc2NyaXB0aW9ucwogICAgICAgICAgICAgICAgICBuYW1lID0gYy5saXN0LAogICAgICAgICAgICAgICAgICBpbWFnZV91cmwgPSBzcmMubGlzdCwKICAgICAgICAgICAgICAgICAgZF9saXN0ID0gZGVzY3IubGlzdAogICAgICAgICAgICAgICAgICApCgoKZGZbMywxXSA9ICJDaW5uYW1vbiBhbmQgQ2F5ZW5uZSIgI3VwZGF0ZWQgdGhlIG5hbWUgb2YgQ2lubmFtb24gYW5kIENheWVubmUgYmVjYXVzZSBJIGZvdW5kIG91dCBsYXRlciB0aGF0IGJlY2F1c2UgaXQgd2FzIHdyaXR0ZW4gYXMgIkNpbm5hbW9uL0NheWVubmUiLCBzb21lIGZ1bmN0aW9ucyB3ZXJlIGNvbmZ1c2VkIHdpdGggdGhlICIvIiBzeW1ib2wuIAoKCmRmWzExLDFdID0gIlZhbmlsbGEiCgoKYGBgCgoKIyMgQ2xlYW4gYW5kIFByZXBhcmUgVGV4dCBEZXNjcmlwdGlvbnMgb2YgdGhlIENob2NvbGF0ZXMgCiMjIyBBcHBseSByZWFkZXIgZnVuY3Rpb24gdG8gZXh0cmFjdCBjaG9jb2xhdGUgZGVzY3JpcHRpb25zCkkgdGhlbiBjcmVhdGVkIGEgZnVuY3Rpb24gdGhhdCBpcyBnb2luZyB0byB0YWtlIHRoZSBsaW5rIG9mIGVhY2ggY2hvY29sYXRlIGFuZCBnZXQgdGhlIGluZm9ybWF0aW9uLiBJIHVzZWQgdGhpcyBmdW5jdGlvbiBzbyB0aGF0IGl0IGNvdWxkIGJlIGFwcGxpZWQgdG8gZWFjaCBjb2x1bW4uIAoKYGBge3IgaHRtbCByZWFkaW5nIGZ1bmN0aW9ufQpyZWFkZXIgPC0gZnVuY3Rpb24odXJsKSB7CiAgCiAgc2ltcGxlPSByZWFkX2h0bWwodXJsKSAjY2hhbmdlZCB0aGlzIGZyb20gInVybCIuLi5zZWUgaWYgdGhpcyBjaGFuZ2VzIGFueXRoaW5nIAoKIHggPSAgc2ltcGxlICU+JQogIGh0bWxfbm9kZXMoInAiKSAlPiUKICBodG1sX3RleHQoKQogCiBwcmludChwYXN0ZSh4WzFdLCB4WzJdKSwgc2VwID0gIiAiKQogIAp9CgoKYGBgCkkgYXBwbGllZCB0aGUgcmVhZGVyIGZ1bmN0aW9uIHRvIHRoZSB1cmxzIHdpdGggdGV4dHVhbCBkYXRhIHNvIEkgY291bGQgc3lzdGVtYXRpY2FsbHkgZXh0cmFjdCB0ZXh0LiBJZGVhbGx5LCB5b3Ugc2hvdWxkIG9ubHkgbmVlZCB0byBleHRyYWN0IGFuZCBydW4gdGhpcyBmdW5jdGlvbiBvbmx5IG9uY2Ugc28gdGhhdCB5b3UgYXJlIG5vdCBzY3JhcGluZyB0aGUgd2VicGFnZSBlYWNoIHRpbWUuIAoKYGBge3IgR2V0dGluZyB0ZXh0IHVzaW5nIHRoZSByZWFkZXIgZnVuY3Rpb259CgpkZiRkX2xpc3QgPC1hcy5jaGFyYWN0ZXIoZGYkZF9saXN0KQpkZlsidGV4dCJdID0gc2FwcGx5KGRmJGRfbGlzdCwgcmVhZGVyKQpkZiRpbWFnZV91cmwgPC1hcy5jaGFyYWN0ZXIoZGYkaW1hZ2VfdXJsKQoKCmBgYAoKIyMjIFRva2VuaXplIGFuZCBjbGVhbiBjaG9jb2xhdGUgZGVzY3JpcHRpb25zIApJbiB0aGlzIHN0ZXAsIEkgY2xlYW5lZCB0aGUgdGV4dHVhbCBkYXRhIG9mIHRoZSBjaG9jb2xhdGUgZGVzY3JpcHRpb24gdXNpbmcgdGhlIG1ldGhvZG9sb2d5IGZyb20gRXhlcmNpc2UgNS4gCgpgYGB7cn0KIyMgQ2xlYW4gZGF0YSBieSAic2VhcmNoZXMgYW5kIHJlcGxhY2UiIHN0YXRlbWVudHMgCmRmJHRleHQgPSBnc3ViKCdbMC05XSsnLCAnJywgZGYkdGV4dCkgIyBSZW1vdmVzIHdvcmRzIHRoYXQgaW5jbHVkZSBudW1iZXJzCmRmJHRleHQgPSBnc3ViKCdbLl0rJywgJycsIGRmJHRleHQpICMgUmVtb3ZlcyB3b3JkcyB3aXRoIHBlcmlvZHMKZGYkdGV4dCA9IGdzdWIoJ2RvaScsICcnLCBkZiR0ZXh0KSAjIFJlbW92ZXMgbm9uLXdvcmQgImRvaSIKZGYkdGV4dCA9IGdzdWIoJ2ZpZycsICcnLCBkZiR0ZXh0KSAjCmRmJHRleHQgPSBnc3ViKCd6aWonLCAnJywgZGYkdGV4dCkgCmRmJHRleHQgPSBnc3ViKCduaWInLCAnJywgZGYkdGV4dCkgCmRmJHRleHQgPSBnc3ViKCJpdCdzIiwgJycsIGRmJHRleHQpIApkZiR0ZXh0ID0gZ3N1YigiSXQncyIsICcnLCBkZiR0ZXh0KSAKZGYkdGV4dCA9IGdzdWIoIml0IiwgJycsIGRmJHRleHQpIApkZiR0ZXh0ID0gZ3N1YigiVHQiLCAnJywgZGYkdGV4dCkgCmRmJHRleHQgPSBnc3ViKCJsaWtlIiwgJycsIGRmJHRleHQpCmRmJHRleHQgPSBnc3ViKCJqdXN0IiwgJycsIGRmJHRleHQpIApkZiR0ZXh0ID0gZ3N1YigibWFkaXNvbiIsICcnLCBkZiR0ZXh0KQpkZiR0ZXh0ID0gZ3N1YigiTWFkaXNvbiIsICcnLCBkZiR0ZXh0KQpkZiR0ZXh0ID0gZ3N1YigibWFrZSIsICcnLCBkZiR0ZXh0KQpkZiR0ZXh0ID0gZ3N1Yigia2l0Y2hlbiIsICcnLCBkZiR0ZXh0KQoKYGBgCgoKYGBge3IgdG9rZW5pemVfdGV4dH0KIyMgVG9rZW5pemUgYmFzZWQgb24gd29yZCBhcyB0b2tlbiBhbmQgcmVtb3ZlIHB1bmN0dWF0aW9uIGFuZCBjb252ZXJ0IHRvIGxvd2VyIGNhc2UKdGV4dC5kZiA9IGRmICU+JSAKICAgIHVubmVzdF90b2tlbnModGVybSwgdGV4dCwgdG9rZW4gPSAid29yZHMiLCAKICAgICAgICAgICAgICAgICB0b19sb3dlciA9IFRSVUUsIAogICAgICAgICAgICAgICAgIHN0cmlwX3B1bmN0ID0gVFJVRSkgCiAgCiMjIFJlbW92ZSBvbmUtbGV0dGVyIGFuZCB0d28tbGV0dGVyIHdvcmRzCiAgdGV4dC5kZiA9IHRleHQuZGYgJT4lIGZpbHRlcihzdHJfbGVuZ3RoKHRlcm0pPjIpCiAgCiMjIFJlbW92ZSB2ZXJ5IGxvbmcgd29yZHMtLXNwdXJpb3VzIHdvcmRzIGNyZWF0ZWQgYnkgcGRmIHJlYWRlcgogIHRleHQuZGYgPSB0ZXh0LmRmICU+JSBmaWx0ZXIoc3RyX2xlbmd0aCh0ZXJtKTwxNSkKICAKIyMgUmVtb3ZlIHN0b3B3b3JkcwogIHRleHQuZGYgPSB0ZXh0LmRmICU+JSAKICAgIGFudGlfam9pbihnZXRfc3RvcHdvcmRzKCksIGJ5ID0gYygidGVybSIgPSAid29yZCIpKQogIAoKI1N0ZW0gYW5kIExlbWF0aXplIFdvcmRpbmcKCiB0ZXh0LmRmJHRlcm0gPSBzdGVtX3dvcmRzKHRleHQuZGYkdGVybSkgIyBDb252ZXJ0cyB3b3JkIHRvIGl0cyBzdGVtLCB3aGljaCBtaWdodCBub3QgYmUgYSB3b3JkLCBzdWNoIGFzICJjb21wdXRhdGlvbmFsIiA+PiAiY29tcHV0IgojIFN0ZW0gY29tcGxldGlvbiBjYW4gY29udmVydCBiYWNrIHRvIGEgd29yZCBiYXNlZCBvbiB0aGUgbW9zdCBmcmVxdWVudCBvcmlnaW5hbCBmb3JtCgp0ZXh0LmRmJHRlcm0gPSBsZW1tYXRpemVfd29yZHModGV4dC5kZiR0ZXJtKSAjIFNpbWlsYXIgdG8gc3RlbW1pbmcsIGJ1dCByZXR1cm5zIGEgd29yZCBhbmQgdGFrZXMgbG9uZ2VyCgoKIyMgUGxvdCBudW1iZXIgb2Ygd29yZHMgcmVtYWluaW5nIGFmdGVyIHByb2Nlc3NpbmcgbmFtZXMKdGV4dC5kZiAlPiUgY291bnQobmFtZSkgJT4lIApnZ3Bsb3QoYWVzKG4sIHJlb3JkZXIobmFtZSwgLW4pKSkgKwogIGdlb21fY29sKCkrCiAgbGFicyh4ID0gIlRvdGFsIHdvcmRzIGZvciBlYWNoIGNob2NvbGF0ZSB0eXBlIiwgeSA9ICIgQ2hvY29sYXRlIFR5cGUiKQogIAoKYGBgCgpUaGUgZmlndXJlIGFib3ZlIHNob3dzIHRoZSBudW1iZXIgb2Ygd29yZHMgcmVtYWluaW5nIGFmdGVyIGNsZWFuaW5nIGFuZCBwcmVwcm9jZXNzaW5nIG9mIHRoZSB0ZXh0dWFsIGRhdGEuIEVhY2ggY2hvY29sYXRlIHNlZW1zIHRvIGhhdmUgYSBzaW1pbGFyIG51bWJlciBvZiB3b3JkcyByZW1haW5pbmcsIHNvIHdlIGFyZSBub3QgdG9vIGNvbmNlcm5lZCB3aXRoIGVsaW1pbmF0aW5nIHRvbyBtYW55IHdvcmRzIGZyb20gdGhlIGRhdGEuCgojIyMgV2VpZ2h0IHRlcm0gZnJlcXVlbmN5LCBmaWx0ZXIsIGFuZCB2aXN1YWxpemUgdGVybXMgdXNpbmcgVEZJREYKVGhlIG1vcmUgb2Z0ZW4gYSB0ZXJtIG9jY3VycyBpbiBhIG5hbWUgdGhlIG1vcmUgaW5kaWNhdGl2ZSBpdCBpcyBvZiB0aGUgbmFtZSdzIGNvbnRlbnQgdW5sZXNzIGl0IHRlcm0gb2NjdXJzIGZyZXF1ZW50bHkgaW4gbW9zdCBuYW1lcy4gVGVybSBpbXBvcnRhbmNlIGNhbiBiZSBjYWxjdWxhdGVkIGFzIGEgY29tYmluYXRpb24gb2YgdGhlIGxvY2FsIGFuZCBnbG9iYWwgZnJlcXVlbmN5IHVzaW5nIHdpdGhpbi1uYW1lIHRlcm0gZnJlcXVlbmN5IChURikgYW5kIHRoZSBpbnZlcnNlIG9mIGl0cyBmcmVxdWVuY3kgYWNyb3NzIG5hbWVzIChJREYpLiAKUmVmZXJlbmNlOiBodHRwczovL3d3dy50aWR5dGV4dG1pbmluZy5jb20vdGZpZGYuaHRtbAoKYGBge3J9CiMjIENhbGN1bGF0ZSB0ZXJtIGZyZXF1ZW5jeSBhbmQgYWRkIHRmX2lkZiB2YXJpYWJsZXMKdGZpZGYudGV4dC5kZiA9IHRleHQuZGYgJT4lIGNvdW50KG5hbWUsIHRlcm0pICU+JSAKICBiaW5kX3RmX2lkZih0ZXJtLCBuYW1lLCBuKQoKCnRmaWRmLnRleHQuZGYKCmBgYApJIGNyZWF0ZWQgdGhlIHBsb3RzIGZyb20gRXhlcmNpc2UgNSB0byBmdXJ0aGVyIHVuZGVyc3RhbmQgdGhlIGRhdGEuICBUaGUgY2h1bmsgYmVsb3cgaXMgdGFraW5nIHRoZSBkYXRhZnJhbWUgd2UgY3JlYXRlZCBhYm92ZSwgYW5kIGdldHRpbmcgdGhlIHRvcCB0Zl9pZGYgZm9yIGVhY2ggb2YgdGhlIGNob2NvbGF0ZXMsIHNvIHdlIGNhbiBkZXRlcm1pbmUgdGhlIG1vc3QgZGVmaW5pbmcgd29yZHMgZm9yIHRoZSBjaG9jb2xhdGUuIEJlY2F1c2UgdGhlcmUgd2VyZSBub3QgYSBsb3Qgb2Ygd29yZHMgYW5kIG1hbnkgZGlzaW5jdGl2ZSB3b3JkcywgSSBzZXQgbiAodGhlIG51bWJlciAgb2Ygcm93cykgaW4gdG9wX24gdG8gYmUgMy4gCiAKYGBge3J9CiMjIFBsb3QgbW9zdCBkaXNjcmltaW5hdGluZyB0ZXJtcwp0b3AuZGYgPSB0ZmlkZi50ZXh0LmRmICU+JSBncm91cF9ieShuYW1lKSAlPiUgdG9wX24oMywgdGZfaWRmKSAlPiUgCiAgdW5ncm91cCgpICU+JSAKICBtdXRhdGUobmFtZSA9IGFzLmZhY3RvcihuYW1lKSkKCmBgYApUaGUgZmlyc3QgcGxvdCBiZWxvdyBwcm92aWRlcyBpbnNpZ2h0IGludG8gdGhlIG1vc3QgZGVmaW5pbmcgd29yZHMgb2YgZWFjaCBjaG9jb2xhdGUuIE11bHRpcGxlIHdvcmRzIGFwcGVhciBmb3Igc29tZSBjaG9jb2xhdGVzIGJlY2F1c2UgbXVsdGlwbGUgd29yZHMgY2FuIGFwcGVhciB3aXRoIGEgc2ltaWxhciBmcmVxdWVuY3kgaW4gZWFjaCBjaG9jb2xhdGUuIFRoZSBzZWNvbmQgcGxvdCBpbnZlc3RpZ2F0ZXMgdGhlIHRmIHZzLiB0aGUgaWRmIGluIGVhY2ggY2hvY29sYXRlLiBUaGlzIGlzIHVzZWZ1bCBmb3IgdW5kZXJzdGFuZGluZyBob3cgb2Z0ZW4gYSB3b3JkIGFwcGVhcnMgZm9yIGEgcGFydGljdWxhciBjaG9jb2xhdGUgdnMuIGhvdyBvZnRlbiBpdCBhcHBlYXJzIGFjcm9zcyBhbGwgb2YgdGhlIGNob2NvbGF0ZXMuIEZvciBleGFtcGxlLCBpdCBtYWtlcyBzZW5zZSB0aGF0IGJsdWViZXJyeSBpcyB2ZXJ5IGZyZXF1ZW50IGZvciB0aGUgYmx1ZWJlcnJ5IGNob2NvYWx0ZSwgYW5kIGl0IGFsc28gZG9lcyBub3QgYXBwZWFyIGluIHRoZSBvdGhlciBjaG9jb2xhdGVzLgoKYGBge3IgdGZfaWRmLCBmaWcuaGVpZ2h0PTQuNX0KZ2dwbG90KHRvcC5kZiwgYWVzKHJlb3JkZXJfd2l0aGluKHRlcm0sIHRmX2lkZiwgd2l0aGluID0gbmFtZSksIHRmX2lkZikpICsgIyNpbmNyZWFzZSB0aGUgc3BhY2luZyBiZXR3ZWVuIHRoZSB3b3Jkcz8KICBnZW9tX2NvbCgpICsKICBjb29yZF9mbGlwKCkgKwogIGZhY2V0X3dyYXAoLn5uYW1lLCBzY2FsZXMgPSAiZnJlZSIpKwogIHNjYWxlX3hfcmVvcmRlcmVkKCkgCgojIFNjYXR0ZXJwbG90IG9mIHRlcm0gZnJlcXVlbmN5IGFuZCBpbnZlcnNlIG5hbWUgZnJlcXVlbmN5IGZvciBlYWNoIG5hbWUKZ2dwbG90KHRvcC5kZiwgYWVzKGlkZiwgdGYsIHNpemUgPSB0Zl9pZGYpKSArCiAgZ2VvbV9wb2ludChzaGFwZSA9IDIxLCBzaXplID0gLjc1KSArCiAgZ2VvbV90ZXh0X3JlcGVsKGFlcyhsYWJlbCA9IHRlcm0sIHNpemUgPSB0Zl9pZGYpKSArCiAgZmFjZXRfd3JhcCgufm5hbWUpICsKICB0aGVtZV9idygpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCgojIyBBIHNpbmdsZSBwbG90IG9mIHRoZSB0b3AgdGZfaWRmIHRlcm1zIGFjcm9zcyBhbGwgbmFtZXMKZ2dwbG90KHRvcC5kZiwgYWVzKGlkZiwgdGYsIHNpemUgPSB0Zl9pZGYpKSArCiAgZ2VvbV9wb2ludChzaGFwZSA9IDIxLCBzaXplID0gMSkgKwogIGdlb21fdGV4dF9yZXBlbChhZXMobGFiZWwgPSB0ZXJtLCBzaXplID0gdGZfaWRmKSkgKwogIHRoZW1lX2J3KCkgKwogIGNvb3JkX3RyYW5zKHk9ImxvZyIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCgpgYGAKIyMjIExTQSBTcGFjZSBhbmQgQ2hvY29sYXRlIGFuZCBUZXJtIEVtYmVkZGluZ3MKYGBge3J9CiMgQ29udmVydCBmcm9tIHRpZHkgZm9ybWF0IHRvIHRlcm1YQ2hvY29sYXRlIG1hdHJpeAp0ZG1fd2VpZ2h0ZWQudGRtYXQgPSBjYXN0X3RkbSh0ZmlkZi50ZXh0LmRmLCB0ZXJtLCBuYW1lLCB0Zl9pZGYpCnRkbV9jb3VudC50ZG1hdCA9IGNhc3RfdGRtKHRmaWRmLnRleHQuZGYsIHRlcm0sIG5hbWUsIG4pCgpsc2FfbW9kZWwgPC0gbHNhKHRkbV9jb3VudC50ZG1hdCwgIGRpbXM9ZGltY2FsY19zaGFyZShzaGFyZSA9IC43NSkpIAojIGRpbWNhbGNfc2hhcmUgcmV0YWlucyB0aGF0IGRpbWVuc2lvbnMgdGhhdCByZXRhaW4gdGhlIHJlcXVpcmVkIHNoYXJlIG9mIHRoZSB0b3RhbCB2YXJpYW5jZQoKIyMgRGltZW5zaW9ucyBvZiB0aGUgTFNBIHNwYWNlCiMgVGhlIHNpbmd1bGFyIHZhbHVlIGhhcyBhIG1heGltdW0gZGltZW5zaW9ucyBvZiB0aGUgbnVtYmVyIG9mIGNob2NvbGF0ZQpkaW0obHNhX21vZGVsJHRrKSAjIFRlcm1zIHggTFNBIHNwYWNlCgoKYGBgCgpgYGB7cn0KZGltKGxzYV9tb2RlbCRkaykgIyBDaG9jb2NsYXRlIHggTFNBIHNwYWNlCgpgYGAKCmBgYHtyfQpsZW5ndGgobHNhX21vZGVsJHNrKSAjIFNpbmd1bGFyIHZhbHVlcwoKYGBgCgpgYGB7cn0KIyMgU2hvd3MgZXhwZWN0ZWQgdmFsdWUgb2Ygd29yZCBmcmVxdWVuY3kgZm9yIGVhY2ggY2hvY29jb2xhdGUKYXMudGV4dG1hdHJpeChsc2FfbW9kZWwpCmBgYAoKYGBge3J9CiMjIENhbGN1bGF0ZXMgTFNBIG9uIHRmX2lkZiB3ZWlnaHRlZCB0ZXJtcwpsc2FfbW9kZWwgPSBsc2EodGRtX3dlaWdodGVkLnRkbWF0LCAgZGltcz1kaW1jYWxjX3NoYXJlKHNoYXJlID0gLjc1KSkKCnJtKHRkbV9jb3VudC50ZG1hdCkKYGBgCgoKIyMgQ2x1c3RlciBjaG9jb2xhdGVzIGJ5IHRlcm1zLUFHTkVTIHVzaW5nIHRoZSBMU0EgRW1iZWRkaW5ncyAKCgpPbmNlIEkgaGFkIHRoZSB0ZXh0dWFsIGRhdGEgb2YgY2hvY29jbGF0ZXMgZnJvbSB0aGUgTFNBIGVtYmVkZGluZ3MsIEkgY29uZHVjdGVkIEFHTkVTIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHVzaW5nIHRoZSBlbWJlZGRpbmdzLgoKCmBgYHtyfQoKIyMgQ29zaW5lIHNpbWlsYXJpdHkgaXMgZXF1YWwgdG8gMSBmb3IgaWRlbnRpY2FsIGRvY3VtZW50cwpkb2Muc2ltaWxpYXJpdHkubWF0ID0gY29zaW5lKHQobHNhX21vZGVsJGRrKSkgIyBUaGUgZCBjb21wb25lbnQgZGVzY3JpYmVzIHRoZSBkb2N1bWVudHMgCgojIyBDYWxjdWxhdGVzIHRoZSBtZWFuIHRmX2lkZiBvZiBlYWNoIHRlcm0gYW5kIHNlbGVjdHMgdG9wIDcwIAp0ZW1wID0gdGZpZGYudGV4dC5kZiAlPiUgCiAgZ3JvdXBfYnkodGVybSkgJT4lIAogIHN1bW1hcmlzZShtLnRmX2lkZiA9IG1lYW4odGZfaWRmKSkgJT4lIAogIGNiaW5kKGxzYV9tb2RlbCR0aykgJT4lIHRvcF9uKDcwLCBtLnRmX2lkZikgCgojIENvc2luZSBzaW1pbGFyaXR5IG9mIHRlcm1zCnJvdy5uYW1lcyh0ZW1wKT0gdGVtcCR0ZXJtCnRlcm0uc2ltaWxpYXJpdHkubWF0ID0gY29zaW5lKHQodGVtcCAlPiUgc2VsZWN0KC10ZXJtLCAtbS50Zl9pZGYpKSkgCgpkb2MuZGlzc2ltaWxhcml0eS5kaXN0ID0gYXMuZGlzdCgxLWRvYy5zaW1pbGlhcml0eS5tYXQpCnRlcm0uZGlzc2ltaWxhcml0eS5kaXN0ID0gYXMuZGlzdCgxLXRlcm0uc2ltaWxpYXJpdHkubWF0KQoKIyMgSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcKIyBTZXR0aW5nIG1ldGhvZCA9IHdhcmQuZDIgY29ycmVzcG9uZHMgdG8gYWduZXMgY2x1c3RlcmluZwpkb2MuY2x1c3RlciA9IGhjbHVzdChkb2MuZGlzc2ltaWxhcml0eS5kaXN0LCBtZXRob2QgPSAid2FyZC5EMiIsIG1lbWJlcnMgPSBOVUxMKQpkZW5kX2xzYSA8LSBhcy5kZW5kcm9ncmFtIChkb2MuY2x1c3RlcikKCgpgYGAKCgpgYGB7cn0KIyMgQnVpbGQgdGhlIGRlbmRyb2dyYW0gd2l0aCB0aGUgaW1hZ2VzIG9mIHRoZSBjaG9jb2xhdGVzIGZvciB0aGUgTFNBIGVtYmVkZGluZ3MgCgppbWFnZV9sc2EuZGYgPC0gZGF0YS5mcmFtZSh5ID0gc2VxKDEsMzIsIGJ5ID0gMiksCiAgICAgICAgICAgICAgICB4ID0gYyguMSwtLjEsLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsIC0uMSksCiAgICAgICAgICAgICAgICBpbWFnZSA9IGMoIlN3ZWV0IEN1cnJ5IFdpdGggU2FmZnJvbi5qcGVnIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIkNvZ25hYy5qcGVnIiwgICJMZW1vbmdyYXNzIHdpdGggR2luZ2VyLmpwZWciLCJKYXNtaW5lLmpwZWciLCAiUm9zZS5qcGVnIiwgIlZhbmlsbGEuanBlZyIsICJDaW5uYW1vbiBhbmQgQ2F5ZW5uZS5qcGVnIiwgIk1hY2h1IFBpY2NodS5qcGVnIiwgIkJsdWViZXJyeS5qcGVnIiwgIlJhc3BiZXJyeS5qcGVnIiwgIkNhcmFtZWwgU3ByaW5rbGVkIFdpdGggR3JleSBTYWx0LmpwZWciLCAiU2hpaXRha2UgTXVzaHJvb20uanBlZyIsICJFc3ByZXNzby5qcGVnIiwgIkZlYXR1cmVkIFNpbmdsZSBPcmlnaW4uanBlZyIsICJDb2ludHJlYXUuanBlZyIsICJFYXJsIEdyZXkuanBlZyIpKQoKY2hvY19kZW5kID0gZ2dkZW5kcm9ncmFtKGRlbmRfbHNhLCByb3RhdGUgPSBUUlVFLCB0aGVtZV9kZW5kcm8gPSBUUlVFLCBjZXggPSAxMDApICMrIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KHNpemU9MTQpKQoKCiNnZ2RlbmRyb2dyYW0oZGVuZDEsIHJvdGF0ZSA9IFRSVUUsIHRoZW1lX2RlbmRybyA9IFRSVUUpCmxhYmVscyA9IGdncGxvdChpbWFnZV9sc2EuZGYsIGFlcyh4LCB5KSkgKyBnZW9tX2ltYWdlKGFlcyhpbWFnZT1pbWFnZSksIHNpemU9LjEyNSkgKyAgdGhlbWVfYncoKSArIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSwgcGFuZWwuZ3JpZC5tYWpvciA9IGVsZW1lbnRfYmxhbmsoKSwKcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy5saW5lID0gZWxlbWVudF9saW5lKGNvbG91ciA9ICJ3aGl0ZSIpLCBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50ZXh0LnkgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50aWNrcy55ID0gZWxlbWVudF9ibGFuaygpLCBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSxheGlzLnRpdGxlLnggPSBlbGVtZW50X3RleHQoY29sb3IgPSAid2hpdGUiKSwKYXhpcy50aXRsZS55ID0gZWxlbWVudF9ibGFuaygpKSAgKyB4bGltKC0uMjUsIC4yNSkgCgpsYXlvdXQgPC0gYygKICBhcmVhKHQgPSAxLCBsID0gMSwgYiA9IDEsIHIgPSAyKSwKICBhcmVhKHQgPSAxLCBsID0gMywgYiA9IDEsIHIgPSA0KQopCgoKCmxhYmVscysgY2hvY19kZW5kICtwbG90X2xheW91dChkZXNpZ24gPSBsYXlvdXQpCgpgYGAKIyMgQ2x1c3RlciBjaG9jb2xhdGVzIGJ5IHRlcm1zLUFHTkVTIHVzaW5nIHRoZSBHTE9WRSBFbWJlZGRpbmdzIApJIHdhbnRlZCB0byBzZWUgaG93IHRoZSBlbWJlZGRpbmdzIHVzZWQgY2hhbmdlcyB0aGUgb3V0Y29tZSBvZiB0aGUgZGVuZHJvZ3JhbSwgc28gSSBjcmVhdGVkIHRoZSBzYW1lIGRlbmRyb2dyYW0gdXNpbmcgdGhlIEdMT1ZFIGVtYmVkZGluZ3MuIFlvdSBzaG91bGQgb25seSBuZWVkIHRvIHJlYWQgaW4gdGhlIEdMT1ZFIEVtYmVkZGluZ3Mgb25jZSBhcyB3ZWxsLiAKCgpJbXBvcnQgdGhlIGdsb3ZlIGVtYmVkZGluZ3MgKHNob3VsZCBvbmx5IG5lZWQgdG8gZG8gdGhpcyBvbmNlISkKYGBge3J9CiMjIFNpbWlsYXIgdG8gc2VudGltZW50IGxleGljb24sIHdvcmQgZW1iZWRkaW5ncyBjYW4gYmUgYWRkZWQgdG8gZGVzY3JpYmUgdGhlIHRlcm1zIGluIGRvY3VtZW50cwoKZ2xvdmUgPSByZWFkX2RlbGltKGZpbGUgPSAiZ2xvdmUuNkIvZ2xvdmUuNkIuMzAwZC50eHQiLCAKICAgICAgICAgICAgICAgICAgIHByb2dyZXNzID1GQUxTRSwKICAgICAgICAgICAgICAgICAgICBjb2xfbmFtZXMgPSBGQUxTRSwgZGVsaW0gPSAiICIsIHF1b3RlID0gIiIpCiBuYW1lcyhnbG92ZSlbMV0gPSAidG9rZW4iCmdsb3ZlYy50ZXh0LmRmID0gdGV4dC5kZiAlPiUgCiAgaW5uZXJfam9pbihnbG92ZSwgYnk9YygidGVybSIgPSAidG9rZW4iKSkKYGBgCgoKYGBge3J9CiMjIERvY3VtZW50IGVtYmVkZGluZ3MgY2FuIGJlIGNyZWF0ZWQgYnkgYXZlcmFnaW5nIHRoZSB0ZXJtIGVtYmVkZGluZwpzLmdsb3ZlYy50ZXh0LmRmID0gZ2xvdmVjLnRleHQuZGYgJT4lIAogIGdhdGhlcihrZXkgPSBnbG92ZWNfaWQsIHZhbHVlID0gZ2xvdmFsdWUsIGNvbnRhaW5zKCJYIikpICU+JSAKICBncm91cF9ieShuYW1lLCBnbG92ZWNfaWQpICU+JSAKICBzdW1tYXJpc2UobS5nbG92YWx1ZSA9IG1lYW4oZ2xvdmFsdWUpKSAlPiUgCiAgc3ByZWFkKGtleSA9IGdsb3ZlY19pZCwgdmFsdWUgPSBtLmdsb3ZhbHVlKSAlPiUgCiAgdW5ncm91cCgpCgojIyBDYWxjdWxhdGUgZG9jdW1lbnQgZGlzdGFuY2UgYmFzZWQgb24gY29zaW5lIHNpbWlsYXJpdHkgb2YgZ2VuZXJpYyBlbWJlZGRpbmcgCgpkb2Muc2ltaWxpYXJpdHkubWF0ID0gY29zaW5lKHQocy5nbG92ZWMudGV4dC5kZiAlPiUgc2VsZWN0KGNvbnRhaW5zKCJYIikpICU+JSBhcy5tYXRyaXgoKSkpICAKcm93Lm5hbWVzKGRvYy5zaW1pbGlhcml0eS5tYXQpID0gYXMudmVjdG9yKHMuZ2xvdmVjLnRleHQuZGYkbmFtZSkKCgpkb2MuZGlzc2ltaWxhcml0eS5kaXN0ID0gYXMuZGlzdCgxLWRvYy5zaW1pbGlhcml0eS5tYXQpCgpkb2MuY2x1c3RlciA9IGhjbHVzdChkb2MuZGlzc2ltaWxhcml0eS5kaXN0LCBtZXRob2QgPSAid2FyZC5EMiIsIG1lbWJlcnMgPSBOVUxMKQpkb2MuY2x1c3RlcgoKZGVuZF9nbG92ZSA8LSBhcy5kZW5kcm9ncmFtIChkb2MuY2x1c3RlcikKCiNnZ2RlbmRyb2dyYW0oZGVuZF9nbG92ZSwgcm90YXRlID0gVFJVRSwgdGhlbWVfZGVuZHJvID0gVFJVRSkKCgpgYGAKCgpgYGB7cn0KIyMgQnVpbGQgdGhlIGRlbmRyb2dyYW0gd2l0aCB0aGUgaW1hZ2VzIG9mIHRoZSBjaG9jb2xhdGVzIGZvciB0aGUgR0xPVkUgZW1iZWRkaW5ncyAKaW1hZ2VfZ2xvdmUuZGYgPC0gZGF0YS5mcmFtZSh5ID0gc2VxKDEsMzIsIGJ5ID0gMiksCiAgICAgICAgICAgICAgICB4ID0gYyguMSwtLjEsLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsIC0uMSksCiAgICAgICAgICAgICAgICBpbWFnZSA9IGMoIkxlbW9uZ3Jhc3Mgd2l0aCBHaW5nZXIuanBlZyIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJTaGlpdGFrZSBNdXNocm9vbS5qcGVnIiwgIkNvaW50cmVhdS5qcGVnIiwgIlN3ZWV0IEN1cnJ5IFdpdGggU2FmZnJvbi5qcGVnIiwgIkNvZ25hYy5qcGVnIiwgIlJhc3BiZXJyeS5qcGVnIiwgIkNhcmFtZWwgU3ByaW5rbGVkIFdpdGggR3JleSBTYWx0LmpwZWciLCAiQ2lubmFtb24gYW5kIENheWVubmUuanBlZyIsICJNYWNodSBQaWNjaHUuanBlZyIsICJWYW5pbGxhLmpwZWciLCAiRXNwcmVzc28uanBlZyIsICJGZWF0dXJlZCBTaW5nbGUgT3JpZ2luLmpwZWciLCAiRWFybCBHcmV5LmpwZWciLCAiUm9zZS5qcGVnIiwgIkJsdWViZXJyeS5qcGVnIiwgIkphc21pbmUuanBlZyIpKQoKY2hvY19kZW5kID0gZ2dkZW5kcm9ncmFtKGRlbmRfZ2xvdmUsIHJvdGF0ZSA9IFRSVUUsIHRoZW1lX2RlbmRybyA9IFRSVUUsIGNleCA9IDEwMCkgCgoKbGFiZWxzID0gZ2dwbG90KGltYWdlX2dsb3ZlLmRmLCBhZXMoeCwgeSkpICsgZ2VvbV9pbWFnZShhZXMoaW1hZ2U9aW1hZ2UpLCBzaXplPS4xMjUpICsgIHRoZW1lX2J3KCkgKyB0aGVtZShwYW5lbC5ib3JkZXIgPSBlbGVtZW50X2JsYW5rKCksIHBhbmVsLmdyaWQubWFqb3IgPSBlbGVtZW50X2JsYW5rKCksCnBhbmVsLmdyaWQubWlub3IgPSBlbGVtZW50X2JsYW5rKCksIGF4aXMubGluZSA9IGVsZW1lbnRfbGluZShjb2xvdXIgPSAid2hpdGUiKSwgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGV4dC55ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGlja3MueSA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy50ZXh0LnggPSBlbGVtZW50X2JsYW5rKCksYXhpcy50aXRsZS54ID0gZWxlbWVudF90ZXh0KGNvbG9yID0gIndoaXRlIiksCmF4aXMudGl0bGUueSA9IGVsZW1lbnRfYmxhbmsoKSkgICsgeGxpbSgtLjI1LCAuMjUpIAoKbGF5b3V0IDwtIGMoCiAgYXJlYSh0ID0gMSwgbCA9IDEsIGIgPSAxLCByID0gMiksCiAgYXJlYSh0ID0gMSwgbCA9IDMsIGIgPSAxLCByID0gNCkKKQoKCgpsYWJlbHMrIGNob2NfZGVuZCArcGxvdF9sYXlvdXQoZGVzaWduID0gbGF5b3V0KQpgYGAKCgojIyBDbGVhbiBhbmQgUHJlcGFyZSBNb3JwaG9sb2dpY2FsIGFuZCBUZXh0dXJhbCBGZWF0dXJlcyBvZiBJbWFnZXMKCk15IHN0cmF0ZWd5IGZvciBnZXR0aW5nIGRhdGEgb24gdGhlIGltYWdlcyB3YXMgdG8gdGFrZSB0aGUgZGYgd2UgaGFkIGJ1aWx0IGZvciB0aGUgdGV4dC1hbmFseXNpcyBhbmQgdXNlIHRoZSBVUkxzIHRvIGV4dHJhY3QgaW1hZ2VzIGZyb20gdGhlIHdlYnNpdGUgYW5kIHRoZW4gZXh0cmFjdCB0aGUgaW1hZ2UgZGF0YS4gSW4gdGhpcyBzdGVwLCBJIGFtIGV4dHJhY3RpbmcgdGhlIG1vcnBob2xvZ2ljYWwgZmVhdHVyZXMgYW5kIHRleHR1cmFsIGZlYXR1cmVzIG9mIGltYWdlcy4gVGhlIG1vcnBob2xvZ2ljYWwgZmVhdXRyZXMgcmVsYXRlIHRvIHBoeXNpY2FsIHN0cnVjdHVyZSBvZiBkaWZmZXJlbnQgcmVnaW9ucyBvZiBhbiBpbWFnZS4gVGhlIHRleHR1cmFsIGZlYXR1cmVzIGludmVzdGlnYXRlIHRoZSBzcGF0aWFsIGFycmFuZ2VtZW50cyBhbmQgYW5kIGNvbG9yIGludGVuc2l0aWVzIG9mIGFuIGltYWdlLiBJdCByZWxhdGVzIHRvIHRoZSBwYXR0ZXJucyBpbiB0aGUgcGl4ZWxzIHRoZW1zZWx2ZXMuIApEZXNjcmlwdGlvbiBvZiB0aGUgaGFyYWxpY2sgZmVhdHVyZXM6CmFzbSAtIGFuZ3VsYXIgc2Vjb25kIG1vbWVudCAtLT4gbWVhc3VyZSBvZiB1bmlmb3JtaXR5LiBSZWFjaGVzIGl0J3MgaGlnaGVzdCBwb2ludCB3aGVuIGdyZXkgbGV2ZWwgZGlzdHJpYnV0aW9uIGhhcyBjb25zdGFudCBvciBwZXJpb2RpYyBmb3JtIApjb24gLSBjb250cmFzdCAtLT4gbWVhc3VyZSBvZiBsb2NhbCB2YXJpYXRpb25zIGluIGFuIGltYWdlCmNvciAtIGNvcnJlbGF0aW9uIC0tPiBtZWFzdXJlIG9mIGltYWdlIGxpbmVhcml0eSAoaGlnaCBjb3JyZWxhdGlvbiBtZWFucyB2ZXJ5IGxpbmVhciBpbWFnZSkKdmFyIC0gdmFyaWFuY2UgLS0gPiB2YXJpYW5jZSBpbiB0aGUgdGV4dHVyYWwKaWRtIC0gaW52ZXJzZSBkaWZmZXJlbmNlIG1vbWVudCAgLS0+IG1lYXN1cmUgaW1hZ2UgaG9tb2dlbmVpdHkKc2F2LSBzdW0gYXZlcmFnZQpzdmEgLSBzdW0gdmFyaWFuY2UgCnNlbiAtIHN1bSBlbnRyb3B5CmVudCAtIGVudHJvcHkgLS0+IHJhbmRvbW5lc3MgaW4gdGhlIGludGVuc2l0eSBkaXN0cmlidXRpb24gCmR2YSAtIGRpZmZlcmVuY2UgdmFyaWFuY2UKZGVuIC0gZGlmZmVyZW5jZSBlbnRyb3B5CmYxMiAtIG1lYXN1cmUgb2YgY29ycmVsYXRpb24gLS0+IGluZm9ybWF0aW9uIG1lYXN1cmVzIG9mIGNvcnJlbGF0aW9uCmYxMy0gbWVhc3VlciBvZiBjb3JyZWxhdGlvbiAtLT4gaW5mb3JtYXRpb24gbWVhc3VyZXMgb2YgY29ycmVsYXRpb24KCgpEb3dubG9hZCBqcGVncyBvZiBjaG9jb2xhdGVzIChzaG91bGQgb25seSBuZWVkIHRvIGRvIHRoaXMgb25jZSkKYGBge3J9CmZvciAoaSBpbiAxOm5yb3coZGYpKSAjdXNpbmcgdGhlIHByZXZpb3VzbHkgY29uc3RydWN0ZWQgZGF0YSBmcmFtZSwgd2UgY2FuIHVzZSB0aGUgVVJMcyB0byBnZXQgdGhlIGltYWdlcyBhbmQgZmluZCB0aGUgaW1hZ2UgZmVhdHVyZXMKewogIGNob2NfbmFtZSA9IGRmWyJuYW1lIl1baSxdICNnZXQgdGhlIG5hbWUgb2YgdGhlIGNob2NvbGF0ZQogIHVybCA9IGRmWyJpbWFnZV91cmwiXVtpLF0gI2dldCB0aGUgdXJsIGZvciB0aGUgaW1hZ2Ugb2YgdGhlIGNob2NvbGF0ZSAKICBkb3dubG9hZC5maWxlKHVybCwgcGFzdGUoY2hvY19uYW1lLCIuanBlZyIsIHNlcD0iIiksIG1vZGUgPSAid2IiKSAjZG93bmxvYWQgdGhlIGpwZWcgZmlsZQogIGZpbGVfbmFtZSA9IHBhc3RlKGNob2NfbmFtZSwiLmpwZWciLCBzZXA9IiIpICNzYXZlIHRoZSBqcGVnIGZpbGUgdG8gdGhlIGRpcmVjdG9yeSBmb3IgZWFzeSBhY2Nlc3MKfQoKYGBgCgpgYGB7cn0KI3RoaXMgZ2V0cyBhbGwgb2YgdGhlIG5lY2Vzc2FyeSBqcGVncwojZm9yIChpIGluIDE6bnJvdyhkZikpCmRmX3Rlc3QgPSBkYXRhLmZyYW1lKCkKCiMgZm9yIChpIGluIDE6bnJvdyhkZikpICN1c2luZyB0aGUgcHJldmlvdXNseSBjb25zdHJ1Y3RlZCBkYXRhIGZyYW1lLCB3ZSBjYW4gdXNlIHRoZSBVUkxzIHRvIGdldCB0aGUgaW1hZ2VzIGFuZCBmaW5kIHRoZSBpbWFnZSBmZWF0dXJlcwojIHsKICBjaG9jX25hbWUgPSBkZlsibmFtZSJdWzEsXSAjZ2V0IHRoZSBuYW1lIG9mIHRoZSBjaG9jb2xhdGUKICAKICBmaWxlX25hbWUgPSBwYXN0ZShjaG9jX25hbWUsIi5qcGVnIiwgc2VwPSIiKQogIEltYWdlID0gcmVhZEltYWdlKGZpbGVfbmFtZSkgI3RoaXMgaXMgd2hlcmUgSSBoYWQgdGhlIGlzc3VlIHdpdGggQ2lubmFtb24gYW5kIENheWVubmUgIAogIAogIEltYWdlMzwtZ2V0RnJhbWUoSW1hZ2UsMikgI0kgaGFkIGFuIGlzc3VlIHdpdGggdGhlIGltYWdlcyBiZWluZyByZWFkIGluIGJ5IFIgYXMgYSB2cFZpZGVvLCBzbyBJIGhhZCB0IHRvIGdyYWIgYSBmcmFtZSBvZiB0aGUgdmlkZW8gZm9yIHRoZSBwcm9jZWVkaW5nIGZ1bmN0aW9ucyB0byB3b3JrLiBJIG5vdGljZWQgdGhhdCB0aGUgc2VsZWN0ZWQgZnJhbWUgZGlkIG5vdCBtYXR0ZXIuIFNvLCBpbiB0aGlzIGluc3RhbmNlIHdlIGFyZSBwaWNraW5nIGZyYW1lIDIuIAogIHggPSB0aHJlc2goSW1hZ2UzLCB3PTQ1LCBoPTQ1LCBvZmZzZXQ9MC4wNSkgI1RoaXMgY3JlYXRlcyB0aGUgIndpbmRvdyIgb2YgdGhlIGltYWdlLiBUaGlzIGlzIGltcG9ydGFudCBiZWNhdXNlIGFsbCBvZiB0aGUgaW1hZ2VzIG5lZWQgdG8gYmUgdGhlIHNhbWUgc2l6ZSBpbiB0aGUgcHJvY2VlZGluZyBzdGVwcy4gSSBmaWd1cmVkIG91dCB3aGNpaCBkaW1lbnNpb25zIHdvcmtlZCBmcm9tIHRyaWFsIGFuZCBlcnJvci4gCiAgCiAgeCA9IG9wZW5pbmcoeCwgbWFrZUJydXNoKDMsIHNoYXBlPSdkaWFtb25kJykpICNvcGVuaW5nIGZ1bmN0aW9uIHJlbW92ZXMgbW9ycGhvbG9naWNhbCBub2lzZSBmcm9tIGltYWdlcyBhbmQgcmVtb3ZlcyBzbWFsbCBvYmplY3RzIGZyb20gdGhlIGJhY2tncm91bmQuIEkgYWRqdXN0ZWQgdGhlIHNpemUgYW5kIHNoYXBlIHRvIHJlYWQgaW4gdGhlIGltYWdlIGFzIGFjY3VyYXRsZXkgYXMgcG9zc2libGUKICB4ID0gYndsYWJlbCh4KSAjSW1hZ2UgbXVzdCBiZSAyRCB0byBiZSBjb21wdXRlIHRoZSBtb3JwaG9sb2dpY2FsIGFuZCB0ZXh0dXIgZmVhdHVyZXMgCiAgI2Rpc3BsYXkoeCkgICN0aGlzIHdpbGwgc2hvdyB5b3Ugd2hhdCB0aGUgaW1hZ2Ugc28geW91IGNhbiBzZWUgaG93IFIgcmVhZHMgdGhlIGltYWdlCiAgZnRzID0gY29tcHV0ZUZlYXR1cmVzLnNoYXBlKHgpICNjb21wdXRpbmcgbW9ycGhvbG9naWNhbCAoc2hhcGUpIGZlYXR1cmVzIG9mIHRoZSBpbWFnZSAKCiNkaXNwbGF5KHgpCiAgCiNiZWdpbiBidWlsZGluZyB0aGUgbW9ycGhvbG9naWNhbCBmZWF0dXJlcwptb3JwaCA9IGZ0cyAlPiUKICBhc190aWJibGUoKSAlPiUKICBtdXRhdGUoYWNyb3NzKC5jb2xzID0gZXZlcnl0aGluZygpLCBsaXN0KG1lYW4gPSBtZWFuLCBzZCA9IHNkKSkpICU+JSAjZXh0cmFjdCB0aGUgbWVhbiBhbmQgc3RhbmRhcmQgbyBkZXZpYXRpb24gb2YgZWFjaCBvZiB0aGUgbW9ycGhvbG9naWNhbCBmZWF0dXJlcyBiZWNhdXNlIHRoZXkgcmV0dXJuIG11bHRpcGxlIHJvd3MgCiAgbXV0YXRlKGNvdW50ID0gbigpKSAlPiUgI2dldCB0aGUgY291bnQgb2YgdGhlIG51bWJlciBvZiAiY2x1c3RlcnMiIGlkZW50aWZpZWQgaW4gdGhlIGltYWdlcwogIHNlbGVjdChzLmFyZWFfbWVhbjpzLnJhZGl1cy5tYXhfbWVhbikgI2V4dHJhY3Qgb25seSB0aGUgbWVhbiBhbmQgc3RhbmRhcmQgZGV2aWF0aW5vcyBvZiBmZWF0dXJlcwoKbW9ycGggPSBoZWFkKG1vcnBoLCAxKSAja2VlcCBvbmx5IHRoZSBmaXJzdCByb3cgCm1vcnBoW2lzLm5hKG1vcnBoKV0gPSAwCgptb3JwaCRuYW1lID0gY2hvY19uYW1lICNzbyB0aGF0IEkgY2FuIGpvaW4gd2l0aCBoYXJhbGljayBmZWF0dXJlcyBsYXRlcgoKdGV4dF9mZWF0IDwtIGNvbXB1dGVGZWF0dXJlcy5oYXJhbGljayh4LCBJbWFnZTMpIyBnZXQgdGV4dHVyYWwgZmVhdHVyZXMgb2YgdGhlIGltYWdlcwoKdGV4dF9mZWF0LmRmID0gYXMuZGF0YS5mcmFtZSh0ZXh0X2ZlYXQpICNjb252ZXJ0IHRvIGRmIHRvIHNpbXBsaWZ5IG1hbmlwdWxhdGlvbiAKCmhhcmFsaWNrRmVhdHVyZXMgPSB0ZXh0X2ZlYXQuZGYgJT4lIAogIGFzX3RpYmJsZSgpICU+JQogIG11dGF0ZShhY3Jvc3MoLmNvbHMgPSBldmVyeXRoaW5nKCksIGxpc3QobWVhbiA9IG1lYW4sIHNkID0gc2QpKSkgJT4lCiAgc2VsZWN0KGguYXNtLnMxX21lYW46aC5mMTMuczJfc2QpICNyZW1vdmUgY29sdW1ucyB0YWh0IGFyZSBub3QgYSBtZWFuIG9yIHNkIHZhbHVlCmhhcmFsaWNrRmVhdHVyZXMgID0gaGVhZChoYXJhbGlja0ZlYXR1cmVzLCAxKSAjcmVtb3ZlIHRoZSBmaXJzdCByb3cgc2luY2UgaXQgZHVwbGljYXRlcwoKaGFyYWxpY2tGZWF0dXJlcyRuYW1lID0gY2hvY19uYW1lICNhc3NpZ24gY2hvY29sYXRlIG5hbWUgc28gdGhhdCBpdCBjYW4gbWVyZ2Ugd2l0aCBtb3JwaCBmZWF0dXJlcyBsYXRlcgoKaGFyYWxpY2tGZWF0dXJlc1tpcy5uYShoYXJhbGlja0ZlYXR1cmVzKV0gPSAwICN0dXJuIGFueSBOQXMgdG8gMAojcHJpbnQoaGFyYWxpY2tGZWF0dXJlcykKCmZpbmFsID0gbWVyZ2UoaGFyYWxpY2tGZWF0dXJlcywgbW9ycGgpICNtZXJnZSB0aGUgbW9ycGhvbG9naWNhbCBhbmQgaGFyYWxpY2sgZmVhdHVyZXMgZm9yIHRoZSBjaG9jb2xhdGUKCmRmX3Rlc3QgPSByYmluZChkZl90ZXN0LCBmaW5hbCkgI01lcmdlIHdpdGggb3RoZXIgcm93cwoKIyB9CgpgYGAKCkkgaW52ZXN0aWdhdGVkIHRoZSBjb2x1bW5zIHRvIHNlZSB3aGF0IGluZm9ybWF0aW9uIG1pZ2h0IGJlIHdvcnRoIGtlZXBpbmcgaW4uIEJhc2VkIG9uIHdoYXQgSSBrbmV3IGFib3V0IHRoZSBkYXRhLCBJIGtuZXcgdGhhdCB0aGUgbW9zdCBvYnZpb3VzIGRpZmZlcmVuY2UgaW4gY2hvY29sYXRlcyB3YXMgd2l0aCB0aGUgY2lubmFtb24vY2F5ZW5uZSBhbmQgdGhlIG90aGVyIGZsYXZvcnMuIFNvLCBJIHdhcyBzdXJlIHRvIGtlZXAgY29sdW1ucyB0aGF0IHNpZ25pZmllZCB0aGlzIGRpZmZlcmVuY2UuIEkgZHJvcHBlZCBjb2x1bW5zIHRoYXQgaGFkIGEgdmVyeSBsYXJnZSBzY2FsZSB0aGF0IG1pZ2h0IGhlYXZpbHkgc2tldyB0aGUgZGlzdGFuY2VzIGluIHRoZSBkYXRhLCBzdWNoIGFzIHRoZSBzdW0gb2YgdGhlIGF2ZXJhZ2VzIGFuZCB0aGUgc3VtIG9mIHRoZSB2YXJpYW5jZXMuIAoKYGBge3J9CmRyb3AuZGYgPSBkZl90ZXN0ICU+JSAgI2Ryb3AgY29sdW1ucyB0aGF0IHdlcmUgbm90IHJlbGV2YW50IGFuZCBpbmNyZWFzZWQgZGVuZHJvZ3JhbSBzY2FsZSBjb25zaWRlcmFibHkKICBzZWxlY3QoLWguc3ZhLnMxX21lYW4sIC1oLnN2YS5zMV9zZCwgLWguc2F2LnMxX21lYW4sIC1oLnNhdi5zMV9zZCwgLWguc3ZhLnMyX21lYW4sIC1oLnN2YS5zMl9zZCwgLWguc2F2LnMyX21lYW4sIC1oLnNhdi5zMl9zZCwgLXMuYXJlYV9tZWFuLCAtcy5hcmVhX3NkLCAtcy5wZXJpbWV0ZXJfbWVhbiwgLXMucGVyaW1ldGVyX3NkLCAtcy5hcmVhX21lYW4sIC1zLmFyZWFfc2QpCgojSSBrZXB0IGFsbCBvZiB0aGUgdGV4dHVyYWwgZmVhdHVyZXMKCgpkcm9wLmRmCgpkcm9wLmRmWzIsMV0gPSAiQ2FyYW1lbCB3aXRoIFNhbHQiCmRyb3AuZGZbOCwxXSA9ICJTaW5nbGUgT3JpZ2luIgpkcm9wLmRmWzEwLDFdID0gIkxlbW9uIGFuZCBHaW5nZXIiCmBgYAoKUHJlcGFyZSBkYXRhIHdpdGggcmVtb3ZpbmcgTkEgYW5kIHNjYWxpbmcuCgpgYGB7cn0KCnNjYWxlZC5kZiA9IGRyb3AuZGYgJT4lIAogIGRyb3BfbmEoKSAlPiUgICMgUmVtb3ZlcyByb3dzIHdpdGggbWlzc2luZyBkYXRhIAogIHNlbGVjdCgtbmFtZSkgJT4lCiAgc2NhbGUoKSAlPiUgYXMuZGF0YS5mcmFtZSgpCgpzY2FsZWQuZGYKCmBgYAoKIyMgQ2x1c3RlciBjaG9jb2xhdGVzIGFuZCBpbWFnZXMtQUdORVMgdXNpbmcgdGhlIFRleHR1cmFsIGFuZCBNb3JwaG9sb2dpY2FsIEZlYXR1cmVzCgpgYGB7cn0KCgpyb3cubmFtZXMoc2NhbGVkLmRmKSA9IGFzLnZlY3Rvcihkcm9wLmRmJG5hbWUpCgoKcmVzLmRpc3QgPSBkaXN0KHNjYWxlZC5kZiwgbWV0aG9kID0gImV1Y2xpZGVhbiIpCmhjMiA8LSBoY2x1c3QocmVzLmRpc3QsIG1ldGhvZCA9ICJ3YXJkLkQyIikgI3VzZXMgYWduZXMgbWV0aG9kCgogZGVuZF9pbSA8LSBhcy5kZW5kcm9ncmFtIChoYzIpCgojZ2dkZW5kcm9ncmFtKGRlbmRfaW0sIHJvdGF0ZSA9IFRSVUUsIHRoZW1lX2RlbmRybyA9IFRSVUUpCgoKCmBgYAogVGhlIHJlc3VsdHMgb2YgdGhlIGltYWdlcyBhcmUgc29tZXdoYXQgYXMgZXhwZWN0ZWQhIFdlIGNhbiBzZWUgdGhhdCBjaW5uYW1vbi9jYXllbm5lIGlzIGluIGl0cyBvd24gZ3JvdXBpbmcsIHdoaWNoIG1ha2VzIHNlbnNlIGJlY2F1c2UgaXQgaXMgcG93ZGVyZWQgYW5kIGhhcyBubyBsdXN0ZXIgaW4gdGhlIGltYWdlLiBJbnRlcmVzdGluZ2x5IGVub3VnaCwgc29tZXRoaW5nIEkgbm90aWNlZCB3YXMgaG93IEVzcHJlc3NvIGlzIG5vdCB3aXRoIENvaW50cmVhdSwgQ29nbmFjIGFuZCBWYW5pbGxhLiBUaGlzIHJldmVhbHMgc29tZSBub2lzZSBpbiB0aGUgZGF0YSBiZWNhdXNlIEVzcHJlc3NvIGhhcyBxdWl0ZSBhIGJpdCBvZiBzaGluZSBvbiB0aGUgdG9wIHdoaWNoIG1ha2UgdGhlIGFsZ29yaXRobSB0aGluayB0aGUgRXNwcmVzc28gaGFzIGEgbG90IG9mIHBhcnRzIG9uIGl0IGluIHRoZSBtaWRkbGUgc2ltaWxhciB0byB0aGUgQmx1ZWJlcnJ5IGFuZCBFYXJsIEdyZXkuIAogCiAKCgogCmBgYHtyfQoKIGltYWdlX210LmRmIDwtIGRhdGEuZnJhbWUoeSA9IHNlcSgxLDMyLCBieSA9IDIpLAogICAgICAgICAgICAgICAgeCA9IGMoLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsLS4xLC4xLC0uMSwuMSwtLjEsLjEsLS4xLC4xLCAtLjEpLAogICAgICAgICAgICAgICAgaW1hZ2UgPSBjKCJDaW5uYW1vbiBhbmQgQ2F5ZW5uZS5qcGVnIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIlNoaWl0YWtlIE11c2hyb29tLmpwZWciLCAiU3dlZXQgQ3VycnkgV2l0aCBTYWZmcm9uLmpwZWciLCAiQ29pbnRyZWF1LmpwZWciLCAiQ29nbmFjLmpwZWciLCAiVmFuaWxsYS5qcGVnIiwgIkZlYXR1cmVkIFNpbmdsZSBPcmlnaW4uanBlZyIsICJDYXJhbWVsIFNwcmlua2xlZCBXaXRoIEdyZXkgU2FsdC5qcGVnIiwgIlJhc3BiZXJyeS5qcGVnIiwgIk1hY2h1IFBpY2NodS5qcGVnIiwgIkphc21pbmUuanBlZyIsICJMZW1vbmdyYXNzIHdpdGggR2luZ2VyLmpwZWciLCAiQmx1ZWJlcnJ5LmpwZWciLCAiRXNwcmVzc28uanBlZyIsICJFYXJsIEdyZXkuanBlZyIsICJSb3NlLmpwZWciKSkKCmNob2NfZGVuZCA9IGdnZGVuZHJvZ3JhbShkZW5kX2ltLCByb3RhdGUgPSBUUlVFLCB0aGVtZV9kZW5kcm8gPSBUUlVFLCBjZXggPSAxMDApIAoKCiNnZ2RlbmRyb2dyYW0oZGVuZDEsIHJvdGF0ZSA9IFRSVUUsIHRoZW1lX2RlbmRybyA9IFRSVUUpCmxhYmVscyA9IGdncGxvdChpbWFnZV9tdC5kZiAsIGFlcyh4LCB5KSkgKyBnZW9tX2ltYWdlKGFlcyhpbWFnZT1pbWFnZSksIHNpemU9LjEyNSkgKyAgdGhlbWVfYncoKSArIHRoZW1lKHBhbmVsLmJvcmRlciA9IGVsZW1lbnRfYmxhbmsoKSwgcGFuZWwuZ3JpZC5tYWpvciA9IGVsZW1lbnRfYmxhbmsoKSwKcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwgYXhpcy5saW5lID0gZWxlbWVudF9saW5lKGNvbG91ciA9ICJ3aGl0ZSIpLCBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50ZXh0LnkgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50aWNrcy55ID0gZWxlbWVudF9ibGFuaygpLCBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSxheGlzLnRpdGxlLnggPSBlbGVtZW50X3RleHQoY29sb3IgPSAid2hpdGUiKSwKYXhpcy50aXRsZS55ID0gZWxlbWVudF9ibGFuaygpKSAgKyB4bGltKC0uMjUsIC4yNSkgCgpsYXlvdXQgPC0gYygKICBhcmVhKHQgPSAxLCBsID0gMSwgYiA9IDEsIHIgPSAyKSwKICBhcmVhKHQgPSAxLCBsID0gMywgYiA9IDEsIHIgPSA0KQopCgoKCmxhYmVscysgY2hvY19kZW5kICtwbG90X2xheW91dChkZXNpZ24gPSBsYXlvdXQpCmBgYAoKTm93IHRoYXQgYWxsIG9mIHRoZSBkZW5kcm9ncmFtcyBhcmUgbWFkZSwgSSB3YW50ZWQgdG8gZW5zdXJlIHRoYXQgdGhleSBoYXZlIGFsbCB0aGUgc2FtZSBsYWJlbHMganVzdCBpbiBjYXNlIQpgYGB7cn0Kc29ydChsYWJlbHMoZGVuZDEpKSA9PSBzb3J0KGxhYmVscyhkZW5kMikpICN2ZXJpZnkgYWxsIHRoZSBsYWJlbHMgYXJlIHRoZSBzYW1lCgpgYGAKCiMjIFRhbmdsZWdyYW1zCgojIyMgVGFuZ2xlZ3JhbSBvZiBHTE9WRSB3b3JkIGVtYmVkZGluZ3MgYW5kIEltYWdlcwoKVGhlIGVuZ3RhbmdsZW1lbnQgbWVhc3VyZXMgdGhlIHF1YWxpdHkgb2YgdGhlIGFsaWdubWVudCBiZXR3ZWVuIHRoZSB0d28gdHJlZXMuIFRoZSBsb3dlciB0aGUgZW50YW5nbGVtZW50IGlzLCB0aGUgYmV0dGVyICAoMSA9ZnVsbCBlbnRhbmdsZW1lbnQsIDAgPSBubyBlbnRhbmdsZW1lbnQpCmBgYHtyfQoKZGVuZCA9IGRlbmRsaXN0KGRlbmQxLCBkZW5kMikgJT4lICNsZWZ0IGhhbmQgc2lkZSBpcyB0aGUgdGV4dHVhbCBkYXRhLCBhbmQgdGhlIHJpZ2h0IGhhbmQgc2lkZSBhcmUgdGhlIGltYWdlcyAKICB1bnRhbmdsZShtZXRob2QgPSAic3RlcDFzaWRlIikgJT4lICMgRmluZCB0aGUgYmVzdCBhbGlnbm1lbnQgbGF5b3V0CiAgdGFuZ2xlZ3JhbShsYWIuY2V4ID0gLjksIG1hcmdpbl9pbm5lciA9IDksIGNvbW1vbl9zdWJ0cmVlc19jb2xvcl9icmFuY2hlcyA9IFRSVUUpICMgQ29sb3IgY29tbW9uIGJyYW5jaGVzKSAgICAgICAgICAgICAgICAgICAgICAgIyBEcmF3IHRoZSB0d28gZGVuZHJvZ3JhbXMKZGVuZCAlPiUgcGxvdChtYWluID0gcGFzdGUoImVudGFuZ2xlbWVudCA9Iiwgcm91bmQoZW50YW5nbGVtZW50KGRlbmQpLCAyKSkpICN0aGUgZW5ndGFuZ2xlbWVudCBtZWFzdXJlcyB0aGUgcXVhbGl0eSBvZiB0aGUgYWxpZ25tZW50IGJldHdlZW4gdGhlIHR3byB0cmVlcy4gVGhlIGxvd2VyIHRoZSBlbnRhbmdsZW1lbnQgaXMsIHRoZSBiZXR0ZXIgICgxID1mdWxsIGVudGFuZ2xlbWVudCwgMCA9IG5vIGVudGFuZ2xlbWVudCkKCgpgYGAKCk15IGNvbmNsdXNpb24gZm9yIHRoaXMgdGFuZ2xlZ3JhbSBpcyB0aGF0IGl0IGlzICJiZXR0ZXIgdGhhbiBub3RoaW5nIi4gCgoKIyMjIFRhbmdsZWdyYW0gb2YgSW1hZ2VzIGFuZCBMU0EgZW1iZWRkaW5ncwoKYGBge3J9CmRlbmQgPSBkZW5kbGlzdChkZW5kMiwgZGVuZDMpICU+JSAjbGVmdCBoYW5kIHNpZGUgaXMgdGhlIHRleHR1YWwgZGF0YSwgYW5kIHRoZSByaWdodCBoYW5kIHNpZGUgYXJlIHRoZSBpbWFnZXMgCiAgdW50YW5nbGUobWV0aG9kID0gInN0ZXAxc2lkZSIpICU+JSAjIEZpbmQgdGhlIGJlc3QgYWxpZ25tZW50IGxheW91dAogIHRhbmdsZWdyYW0obGFiLmNleCA9IC45LCBtYXJnaW5faW5uZXIgPSA5LCBjb21tb25fc3VidHJlZXNfY29sb3JfYnJhbmNoZXMgPSBUUlVFKSAjIENvbG9yIGNvbW1vbiBicmFuY2hlcykgICAgICAgICAgICAgICAgICAgICAgICMgRHJhdyB0aGUgdHdvIGRlbmRyb2dyYW1zCmRlbmQgJT4lIHBsb3QobWFpbiA9IHBhc3RlKCJlbnRhbmdsZW1lbnQgPSIsIHJvdW5kKGVudGFuZ2xlbWVudChkZW5kKSwgMikpKSAjdGhlIGVuZ3RhbmdsZW1lbnQgbWVhc3VyZXMgdGhlIHF1YWxpdHkgb2YgdGhlIGFsaWdubWVudCBiZXR3ZWVuIHRoZSB0d28gdHJlZXMuIFRoZSBsb3dlciB0aGUgZW50YW5nbGVtZW50IGlzLCB0aGUgYmV0dGVyICAoMSA9ZnVsbCBlbnRhbmdsZW1lbnQsIDAgPSBubyBlbnRhbmdsZW1lbnQpCgpgYGAKCgpUYW5nbGVncmFtIGZvciB0aGUgTFNBIGFuZCBpbWFnZXMgcmV2ZWFsIGEgcmVsYXRpdmVseSBoaWdoIGVudGFuZ2xlbWVudC4gTm90IG11Y2ggY29tbW9uYWxpdHkgaW4gdGhlIGNsdXN0ZXJpbmcgcmVzdWx0cy4gCgojIyMgVGFuZ2xlZ3JhbSBvZiBMU0EgZW1iZWRkaW5ncyBhbmQgR0xPVkUgZW1iZWRkaW5ncwpgYGB7cn0KZGVuZCA9IGRlbmRsaXN0KGRlbmQxLCBkZW5kMykgJT4lICNsZWZ0IGhhbmQgc2lkZSBpcyB0aGUgdGV4dHVhbCBkYXRhLCBhbmQgdGhlIHJpZ2h0IGhhbmQgc2lkZSBhcmUgdGhlIGltYWdlcyAKICB1bnRhbmdsZShtZXRob2QgPSAic3RlcDFzaWRlIikgJT4lICMgRmluZCB0aGUgYmVzdCBhbGlnbm1lbnQgbGF5b3V0CiAgdGFuZ2xlZ3JhbShsYWIuY2V4ID0gLjksIG1hcmdpbl9pbm5lciA9IDksIGNvbW1vbl9zdWJ0cmVlc19jb2xvcl9icmFuY2hlcyA9IFRSVUUpICMgQ29sb3IgY29tbW9uIGJyYW5jaGVzKSAgICAgICAgICAgICAgICAgICAgICAgIyBEcmF3IHRoZSB0d28gZGVuZHJvZ3JhbXMKZGVuZCAlPiUgcGxvdChtYWluID0gcGFzdGUoImVudGFuZ2xlbWVudCA9Iiwgcm91bmQoZW50YW5nbGVtZW50KGRlbmQpLCAyKSkpICN0aGUgZW5ndGFuZ2xlbWVudCBtZWFzdXJlcyB0aGUgcXVhbGl0eSBvZiB0aGUgYWxpZ25tZW50IGJldHdlZW4gdGhlIHR3byB0cmVlcy4gVGhlIGxvd2VyIHRoZSBlbnRhbmdsZW1lbnQgaXMsIHRoZSBiZXR0ZXIgICgxID1mdWxsIGVudGFuZ2xlbWVudCwgMCA9IG5vIGVudGFuZ2xlbWVudCkKCgpgYGAKClRhbmdsZWdyYW0gZm9yIHRoZSBMU0EgYW5kIHdvcmQgZW1iZWRkaW5ncyByZXZlYWwgYSByZWxhdGl2ZWx5IGhpZ2ggZW50YW5nbGVtZW50LiBOb3QgbXVjaCBjb21tb25hbGl0eSBpbiB0aGUgY2x1c3RlcmluZyByZXN1bHRzLiBBbiBpbXBvcnRhbnQgdGFrZWF3YXkgaXMgdGhhdCB0aGUgYXBwcm9hY2ggdGFrZW4gd2l0aCB0ZXh0LWFuYWx5c2lzIGNhbiBoaWdobHkgdmFyeSB0aGUgY29uc3RydWN0ZWQgZGVuZHJvZ3JhbS4g